自动搬运

查看原文

来自洛谷，原作者为

	Zilljy258 太沙雕了，，，

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

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

以下是正文

一道简单的并查集......

题目传送门

大体思路：

其实我一开始也没有想到这是并查集的题目，还想了半天，一看题解，恍然大悟——原来这么简单！

主要思想就是从第一场开始，让 PK 的两人尽可能不在一队，这样就能保证同一队的 PK 尽可能地靠后了。

也就是说，如果第 $i$ 场时，两人还没有关系（还没标记为同一队），那么就将互相放到敌队中去；如果两人已经是同一队的关系了，那么输出 $i$（找到答案了），直接结束程序就好了。

思想很简单，但确实难想到（对我这个小蒟蒻来说 QAQ）。

代码：

#include<iostream>
using namespace std;
int f[100001]={0};
int d[100001]={0};
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void hb(int x,int y){
	f[x]=y;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i; //初始化 father 数组。
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x;
		cin>>y;
		int xx=find(x); //这里我提前查找了，能为后面节约一点点时间（虽然就一点点）。
		int yy=find(y);
		if(xx==yy){ //判断是否找到答案，即正在 PK 的两人是否已经是同一队。
			cout<<i<<endl;
			break;
		}
		if(find(d[x])!=yy&&d[x]!=0){ //d[x]!=0 是判断是否还是初始状态。
			hb(find(d[x]),yy);
		}
		if(find(d[y])!=xx&&d[y]!=0){
			hb(find(d[y]),xx);
		}
		d[x]=yy; //标记为敌人。
		d[y]=xx;
	}
	return 0;
} 

总结：

其实这道题还有一点点贪心的成分在，不知道大家有没有感觉到，就是让正在 PK 的两人尽可能不在一队这一操作......