官方题解

题目大意

有 $n$ 个点，$m$ 条边的无向图，如果点 $a$ 和点 $b$ 有一条边，点 $a$ 和点 $c$ 有一条边，而点 $b$ 和点 $c$ 之间没有边，则可以在点 $b$ 和点 $c$ 之间添加一条边，求最多可以添加多少条边。

解题思路

不难发现，在一个连通块内的所有点都可以通过若干次操作使得每两个点之间连上一条边。于是，我们求出每个连通块的大小 $sz$ 和已有边数 $edgs$ ，就可以求出连通块内没有连接的边数 $\frac{sz\times(sz-1)}{2} - edgs$，也就是答案。

可以用并查集维护 $sz$ 以及 $edgs$ 。

时间复杂度 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) x.begin(),x.end()
#define SUM(x) accumulate(all(x),0ll)
const int INF = 1e18+10;
const int N = 200010, M = 1000010;
const int mod = 998244353;
bool rcmp(int a,int b){return a>b;}

struct DSU{
	vector<int>p,sz,edg;
	DSU(){}
	DSU(int n){
		init(n);
	}
	void init(int n){
		p.resize(n+1);
		sz.resize(n+1);
		edg.resize(n+1);
		for(int i=1;i<=n;i++){
			p[i]=i;
			sz[i]=1;
		}
	}

	int find(int x){
		if(p[x]!=x) p[x]=find(p[x]);
		return p[x];
	}

	void merge(int x,int y){
		x=find(x);
		y=find(y);
		if(x>y) swap(x,y);
		edg[x]++;
		if(x==y) return;
		
		p[y]=x;
		sz[x]+=sz[y];
		edg[x]+=edg[y];
	}

	bool same(int x,int y){
		return find(x)==find(y);
	}
};

void solve(){
	int n,m;cin>>n>>m;
	DSU dsu(n);
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		dsu.merge(a,b);
	}

	int res=0;
	for(int i=1;i<=n;i++){
		if(dsu.p[i]==i){
			int num=dsu.sz[i];
			int e=dsu.edg[i];
			res+=num*(num-1)/2-e;
		}
	}
	cout<<res<<endl;
}

signed main(){
	//init();//Prime();
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
//9223372036854775808