样例对,但全WA,蒟蒻求调!!!
查看原帖
样例对,但全WA,蒟蒻求调!!!
1343308
IAKIOI66666楼主2024/6/8 23:06

初学并查集,各位大佬多多关照,谢谢

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,x,y,cnt,f[1010],m[1010];
char c;
int find(int x){
	if(x==f[x])return x;
	return find(f[x]);
}
void merge(int x,int y){
	int a=find(x),b=find(y);
	if(a==b)return;
	f[a]=f[b];return;
} 

int main(){
	cin>>k>>n;
	for(int i=1;i<=k;i++)f[i]=i;
	while(n--){
		cin>>c>>x>>y;
		if(c=='F')merge(x,y);
		else {
			if(m[x]==0)m[x]=find(y);
			else merge(x,m[y]);
			if(m[y]==0)m[y]=find(x);
			else merge(y,m[x]);
		}
	}
	sort(f+1,f+1+k);
	for(int i=2;i<=k;i++)
		if(f[i]!=f[i-1])cnt++;
	cout<<cnt<<endl;
	return 0; 
}
2024/6/8 23:06
加载中...