数论

选择两条边，满足这两条边的4个节点各不相同也就是这两条边不连通暴力的方法$m^2$ 去枚举所有情况肯定是行不通的，不连通的情况不好求，但是两条边联通的答案好.所以$\\$$ans=C(m,2)-选两条边且联通的总数$$\\$选两条边且联通的总数求法就是枚举每个点,每个点$i$的贡献=$c(m_i,2),m_i=$连接点$i$的边数 $\\$$ans=C_{m}^{2}-{\sum_{i=1}^{n}}C_{m_i}^{2}$$\\$ 整体时间复杂度$o(n)$$\\$

代码如下

$cpp$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200000
vector<int>g[N];
long long ans;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	ans = (1ll*m * (m - 1)) / 2;
	for(int i=1;i<=n;i++){
        ans -= (1ll*g[i].size() * (g[i].size() - 1)) / 2;
    }
	cout << ans << '\n';
	return 0;
}

$python$

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    n = int(data[idx])
    m = int(data[idx + 1])
    idx += 2
    
    g = [[] for _ in range(n + 1)]
    
    for _ in range(m):
        x = int(data[idx])
        y = int(data[idx + 1])
        idx += 2
        g[x].append(y)
        g[y].append(x)
    
    ans = (m * (m - 1)) // 2
    
    for i in range(1, n + 1):
        size = len(g[i])
        ans -= (size * (size - 1)) // 2
    
    print(ans)

if __name__ == "__main__":
    main()

$java$

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        List<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            g[x].add(y);
            g[y].add(x);
        }

        long ans = (long) m * (m - 1) / 2;

        for (int i = 1; i <= n; i++) {
            int size = g[i].size();
            ans -= (long) size * (size - 1) / 2;
        }

        System.out.println(ans);
        scanner.close();
    }
}

题目内容

小明拿到了一个无向图，他准备选择两条边，满足这两条边的4个节点各不相同。

小明想知道，有多少种选择边的方案？

输入描述

第一行输入两个正整数$n$和$m$，代表无向图的节点数量和边的数量。

接下来的$m$行，每行输入$2$个正整数$u,v$，代表节点$u$和节点$u$有一条边连接。

$1≤n，m≤10^5$

$1≤u,v≤n$

保证给定的图不包含重边和自环。

输出描述

一个整数，代表选择边的方案数

样例1

输入

4 4
1 2
2 3
3 4
4 1

输出

2

说明

方案1:选择第1条边和第3条边

方案2:选择第2条边和第4条边。