# 洛谷 P1892

xiaoxiao2021-03-01  15

# 题目链接：团伙

#include<iostream> #include<cstring> using namespace std; int father[20001],e[20001]; int find(int x) { if(father[x]!=x) return father[x]=find(father[x]); else return x; } void hebing(int x,int y) { int x1=find(x); int y1=find(y); if(x1!=y1) { father[x1]=y1; } } int main() { memset(e,0,sizeof(e)); memset(father,0,sizeof(father)); char ch; int x,y,m,n,tot=0; cin>>n>>m; for(int i=1; i<=n; i++) father[i]=i; for(int i=1; i<=m; i++) { cin>>ch>>x>>y; if(ch=='F') { hebing(x,y); } if(ch=='E') { if(e[x] != 0 && (find(e[x]) != find(y))) hebing(y,e[x]); // 判断在不在一个集合里面 if(e[y] != 0 && (find(e[y]) != find(x))) hebing(x,e[y]); e[x] = y; e[y] = x; } } for(int i=1; i<=n; i++) if(father[i]==i) tot++; cout<<tot<<endl; return 0; }

#include<iostream> #include<cstring> using namespace std; int father[20001],e[20001]; int find(int x) { if(father[x]!=x) return father[x]=find(father[x]); else return x; } void hebing(int x,int y) { int x1=find(x); int y1=find(y); if(x1!=y1) { father[x1]=y1; } } int main() { memset(e,0,sizeof(e)); memset(father,0,sizeof(father)); char ch; int x,y,m,n,tot=0; cin>>n>>m; for(int i=1; i<=n; i++) father[i]=i; for(int i=1; i<=m; i++) { cin>>ch>>x>>y; if(ch=='F') { hebing(x,y); } if(ch=='E') { if(e[x] != 0 ) hebing(y,e[x]); if(e[y] != 0 ) hebing(x,e[y]); e[x] = y; } } for(int i=1; i<=n; i++) if(father[i]==i) tot++; cout<<tot<<endl; return 0; }