并查集10分,心态已炸,求大佬看看吧(
查看原帖
并查集10分,心态已炸,求大佬看看吧(
432183
JoeBiden2020楼主2021/10/4 00:01

先自己写了一下。10分,就去和题解对照,发现基本上都一样,样例输出了2,这是怎么回事啊,查了一个小时没差出错

#include <bits/stdc++.h>
using namespace std;
int f[100003],n,m,p,q,ans=0;
bool a[1001][1001];
char opt;
int find(int k){
	if(f[k]==k)return k;
	else return f[k]=find(f[k]);
}
int combine(int x,int y){
	int f1=find(x),f2=find(y);
	f[f2]=f1;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(register int i=1;i<=n;i++)f[i]=i;
	for(register int i=1;i<=m;i++){
		cin>>opt>>p>>q;
		if(opt=='F'){
			combine(p,q);
		}
		else if(opt=='E'){
			a[p][q]=a[q][p]=1;
			for(register int j=1;j<=n;j++){
				if(a[p][j]){
					combine(j,p); 
				}
				if(a[q][j]){
					combine(j,q);
				}
			}
		} 
	}
	for(register int i=1;i<=n;i++){
		if(f[i]==i)ans++;
	}
	cout<<ans; 
} 
2021/10/4 00:01
加载中...