并查集
重点是如何理解：敌人的敌人是朋友 这句话。
思路一：用一个结构体把敌人都存起来，然后循环找队友。这样做这个题也是可以 AC 的，因为这个题的数据比较小，但是对于较大范围的数据可能就不一定能过了。
思路二：只用一个一维数组来存最近的敌人，因为前面的敌人已经被合并过了。
通过思路二，可以节省大量的时间，如果数据规模大的话也能 AC !
#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; }
不过，稍微再改改，就是 0ms 了
#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; }
