求助样例输出'2'的缘故!
查看原帖
求助样例输出'2'的缘故!
394167
Cure_Wing楼主2022/2/3 23:09
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[2222],dep[2222],b,c,ans;
char a;
int find(int x){
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	dep[fa[x]]=min(dep[fa[x]],fa[x]+1);
	return fa[x];
}
void join(int b,int c){
	int fu=find(b),fv=find(c);
	if(fu==fv) return ;
	if(dep[fu]<dep[fv]) swap(fu,fv);
	fa[fv]=fu;
	if(dep[fu]==dep[fv]) ++dep[fu];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=2*n;++i)
		fa[i]=i,dep[i]=1;
	for(int i=1;i<=m;++i){
		scanf("\n%c%d%d",&a,&b,&c);
//        printf("%c %d %d\n",a,b,c);
		if(a=='F')
			join(b,c);
		else{
			join(b+n,c);
			join(b,c+n);
		}
	}
	for(int i=1;i<=n;++i)
		ans+=(fa[i]==i)/*,printf("%d %d %d\n",fa[i],i,fa[i]==i)*/;
	printf("%d\n",ans);
	return 0;
}
2022/2/3 23:09
加载中...