裸的并查集。
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000+10; const int maxm=5000+10; int n,m; int f[maxn]; int vis[maxn]; int e[maxm]; void init() { freopen("gang.in","r",stdin); freopen("gang.out","w",stdout); } int find(int x) { return f[x] == x ? x : f[x]=find(f[x]); } void readdata() { scanf("%d%d\n",&n,&m); char s;int x,y; for(int i=1;i<=n;i++) f[i]=i; memset(e,0,sizeof(e)); for(int i=1;i<=m;i++) { scanf("%c%d%d\n",&s,&x,&y); if(s=='F') { f[find(x)]=find(y); } if(s=='E') { if(e[x]==0) { e[x]=y; } else { if(f[find(e[x])]!=find(y)) f[find(e[x])]=find(y); } if(e[y]==0) { e[y]=x; } else { if(f[find(e[y])]!=find(x)) f[find(e[y])]=find(x); } } } } void work() { memset(vis,0,sizeof(vis)); int ans=0; for(int i=1;i<=n;i++) { if(vis[find(i)]) continue; vis[find(i)]=1; ans++; } printf("%d",ans); } int main() { init(); readdata(); work(); return 0; }