90,WA第七个数据
查看原帖
90,WA第七个数据
1138579
Lazy_Durant楼主2024/1/20 10:54
#include<iostream>
#include<set>
using namespace std;
int f[100010],n,m,opt,a,b;
int find(int x){
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
int main(){
	set<int> q; 
	char op;
	cin>>n>>m;
	for(int i=1;i<=n*2;i++) f[i]=i;
	while(m--){
		cin>>opt>>a>>b;
		if(opt=='F') f[find(b)]=find(a);
		else f[find(b)]=find(a+n);
	}
	for(int i=1;i<=n;i++) q.insert(find(i));
	cout<<q.size();
	return 0;
} 

思路是开2*n个空间,目的是给每个人都设置一个敌人,例如假设n=4,那1和5就是敌人,如果我们读入数据为E 1 2,那就将2与5连在一起(敌人的敌人就是朋友),如果是F 1 2,那就将1和2连在一起,最后检查1-n的祖宗接节点,set去重,求大佬修改,90,wa一个数据

2024/1/20 10:54
加载中...