洛谷 P1892

xiaoxiao2021-03-01  15

题目链接:团伙

并查集

重点是如何理解:敌人的敌人是朋友 这句话。

思路一:用一个结构体把敌人都存起来,然后循环找队友。这样做这个题也是可以 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; }

 

转载请注明原文地址: https://www.6miu.com/read-4050198.html

最新回复(0)