启发式合并 [USACO22DEC] Making Friends P

题意

\(N\) 牛 \(M\) 关系，按照编号从小到大，牛依次离开，每一头牛离开时它认识的牛会互相认识，求最后新增了多少朋友关系。

\(N,M\le 2\times 10^5\)

解法

我们将操作看成每个点边集合的合并，尝试使用启发式合并解决问题。

但是直接做又发现没有办法搞，因为我们会算重很多，于是我们选择仅仅连一条边，从编号小到编号大。

这个样子我们并不会错过什么，因为边集的合并是从小节点开始的，我们贪心选择相连的最小节点合并一定是不劣的，所以就做完了，复杂度就是标准的启发式合并。

代码↓

点击查看代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int n, m, ans=0; set <int> G[MN];
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m; ans=-m;for(int i=1; i<=m; ++i){int u, v; cin>>u>>v;G[min(u,v)].insert(max(u,v));}for(int i=1; i<=n; ++i){if(G[i].empty()) continue;ans+=G[i].size();int u=*G[i].begin();//最小的辣个G[i].erase(G[i].begin());if(G[u].size()<G[i].size()) swap(G[u],G[i]);for(auto v:G[i]) G[u].insert(v);}cout<<ans<<'\n';return 0;
}