New Friends（并查集）

思路：这题应该如何运用并查集呢，我们可以知道一个图有n个点的话我们最多可以建造(n - 1) * n / 2条边，那么我们该如何记录有多少条边以及多少个点呢，我们用siz记录点的个数，边该如何记录呢？我们可以重新开一个数组cnt用来记录每一个连通块的边的数量，每有一条边的话，如果他们联通的话，我们直接将他们所在的连通块+1，否则的话我们将他们的连通块合并后在+1，注意我们应该先求他们的祖先a = finds(u), b = finds(v), 然后将这两个进行比较即可，记住了啊

AC代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll>PII;
const int N=2e5+10;
const int MOD = 9901;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e9 + 7;

ll p[N], siz[N];
ll cnt[N];//记录相同的祖先数量
int finds(int x)
{
	if(x != p[x]) p[x] = finds(p[x]);
	return p[x];
}
int main()
{
    int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) siz[i] = 1, p[i] = i;
	for(int i = 1; i <= m; i ++)
	{
		int u, v;
		cin >> u >> v;
		int a = finds(u), b = finds(v);
		if(a == b)
		{
			cnt[a] ++;
			continue;
		}
		if(a > b) swap(a, b);
		p[b] = a;
		siz[a] += siz[b];
		cnt[a] += cnt[b] + 1;
	}
	ll s = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(p[finds(i)] == i) 
		{
			if(siz[i])
			s += max((ll)0, ((siz[i] - 1) * siz[i] / 2) - cnt[i]);
		}
	}
	cout << s << endl;
	return 0;
}