90pts求调
查看原帖
90pts求调
534025
gmllsswzw楼主2022/10/8 21:32
#include<bits/stdc++.h>
using namespace std;
int n,m,p,q,fa[1005],fa1[1005],ans;
char opt;
int tot,head[10005],to[10005],Next[10005];
void add_edge(int x,int y){
	to[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
}
set<int> s;
int find(int x){
	if(x==fa[x])	return x;
	else
		return	fa[x]=find(fa[x]); 
}
void merge(int x,int y){
	if(find(y)!=find(x))
		fa[find(y)]=find(x);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++){
		cin>>opt>>p>>q;;
		if(opt=='F')	merge(p,q);
		else{
			add_edge(p,q);
			add_edge(q,p);
			fa1[q]=p;	fa1[p]=q;
		}
	}
	for(int i=1;i<=n;i++){
		if(i!=find(fa[i]))
			for(int j=head[fa1[i]];j;j=Next[j])
				if(i!=to[j])
					merge(i,to[j]);
	}
	for(int i=1;i<=n;i++)
		s.insert(find(fa[i]));
	ans=s.size();
	cout<<ans;
	return 0;
}

有哪里思路不清晰的请诸位大佬随时提问QWQ

2022/10/8 21:32
加载中...