自动搬运

查看原文

来自洛谷，原作者为

	EXODUS I love you this much

搬运于2025-08-24 22:43:38，当前版本为作者最后更新于2022-12-25 22:10:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1：前言

谢谢这道题让我意识到我在启发式合并方面一窍不通。

感觉这是 Pt 组最简单的一题

Part 2：正文

考虑一个性质，每次互相连边显然有些多余，不妨转化成将编号最小的点和其它点连边。

考虑正确性，若一头牛 $x$ 出队，不妨设与他相连且编号大于他的牛的编号排序后的结果为 $y_1,y_2,...,y_k$，我们这种连边策略相当于延时连边，即在 $y_1$ 出队以前连接 $y_1\rightarrow y_2,y_3,\ldots y_k$，$y_2$ 出队以前连接 $y_2\rightarrow y_3,\ldots y_k$，每条应当连的边都被连上了至少一次，故存在充分性，所以正确。

直接连边复杂度是 $O(n^2)$，启发式合并 set 后复杂度是 $O(m\log^2n)$ 可以通过此题。

Part 3：代码

const int N=2e5+7;
int n,m;
set<int>g[N];

void Main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		g[min(u,v)].insert(max(u,v));
	}
	ll ans=-m;
	for(int i=1;i<=n;i++){
		if(g[i].empty())continue;
		ans+=g[i].size();
		int u=*g[i].begin(),v=i;g[v].erase(g[v].begin());
		if(g[u].size()<g[v].size())swap(g[u],g[v]);
		for(auto i:g[v])g[u].insert(i);
	}
	cout<<ans;
	return;
}