20pts求助
查看原帖
20pts求助
1304256
xy_mc楼主2024/12/22 11:03

#1#7 AC

#include<bits/stdc++.h>
#define reg register
#define int long long
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
using namespace std;
int n,m,p,q,f[1005],ans,t[1005],d[1005];
char c; 
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y){
	if(find(x)!=find(y)) f[find(y)]=find(x);
	return;
}
signed main(){
	cin>>n>>m;
	rep(i,1,n) f[i]=i;
	rep(i,1,m){
		cin>>c>>p>>q;
		if(c=='F') merge(p,q);
		else{
			if(!d[p]) d[p]=q;
			else merge(p,d[p]);
			if(!d[q]) d[q]=p;
			else merge(q,d[q]);
		}
	}
	rep(i,1,n) t[find(i)]++;
	rep(i,1,n) if(t[i]) ans++;
	cout<<ans; 
	return 0;
}
2024/12/22 11:03
加载中...