写篇题解以防自己忘记。

Solution

我们可以按照一定顺序来加边。注意到新加的边 $b\rightarrow c$ 满足 $a<b<c$，也就是新加的边只会影响大于自己的点，并不会影响小于自己的点。因此这启发我们从 $1$ 到 $n$ 依次遍历每一个点加边。但是直接加边是不行的，这里考虑使用 set 来维护。set 里边存的是和当前这个点有关联的点。留在 set 中的点最终都与点 $i$ 连边，且 $i$ 也只和这些点连边。然后由于是从小到大遍历，因此可以直接将点 $i$ 相关的点的信息传给最小的与 $i$ 相关的点，以保证 $a<b<c$ 时，$b\rightarrow c$。然后就是传信息这一步，使用启发式合并。时间复杂度 $O(n\log^2 n)$。

讲起来有点乱，在代码里面打了注释，挺好懂的。

:::success[code]

#include <bits/stdc++.h>
using namespace std;
int n,m,u,v;
long long ans;
set<int> s[200005];
int main(){
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
		cin>>u>>v,s[min(u,v)].insert(max(u,v));
	for(int i = 1;i<=n;i++){
		if(s[i].empty()) continue;
		ans+=s[i].size();//当前点 i 与且仅与 s[i] 中的点连边（有向图中的出边，这里将无向图看做有向图，因为意义相同）
		int to=*s[i].begin();s[i].erase(s[i].begin());//这里记得删掉自己
		if(s[to].size()<s[i].size()) swap(s[to],s[i]);//启发式合并
		for(auto t:s[i]) s[to].insert(t);
		/*
		这里解释一下为什么不给剩下的点传信息。
		假设 s[i] 中有 a,b,c
		我们只给 s[a] 传 b,c
		也就意味着只传 a->b 和 a->c
		b->c 呢？
		其实 a 中的信息一定会将 c 传给 b
		这是一级一级传上去的
		*/
	}
	cout<<ans;
}