1 /* 2 題目大意：有兩個(gè)不同的黑幫，開(kāi)始的時(shí)候不清楚每個(gè)人是屬于哪個(gè)的！ 3 執(zhí)行兩個(gè)操作 4 A a, b回答a, b兩個(gè)人是否在同一幫派，或者不確定 5 D a, b表示a, b兩個(gè)人不在同一個(gè)幫派 6 7 思路：利用并查集將相同幫派的人合并到一起！ 8 a ,b 不在同一個(gè)城市，那么 a, 和mark[b]就在同一個(gè)城市， 9 b 和 mark[a]就在同一個(gè)城市！ 10 */ 11 #include<iostream> 12 #include<cstring> 13 #include<cstdio> 14 #define M 100005 15 using namespace std; 16 int f[M]; 17 int mark[M];//mark[i]表示 i 與 mark[i]不在同一個(gè)黑幫 18 int rank[M];//為不同的集合的父親節(jié)點(diǎn)記錄其孩子機(jī)節(jié)點(diǎn)個(gè)數(shù)，在合并集合的時(shí)候，將 19 int n, m; //rank 值小的集合連接到 rank 值大的集合上去！ 這樣在路徑壓縮的時(shí)候省去不少時(shí)間 20 21 void init(){ 22 23 memset(mark, 0, sizeof(int)*(n+1)); 24 memset(rank, 0, sizeof(int)*(n+1)); 25 for(int i=1; i<=n; ++i) 26 f[i]=i; 27 } 28 29 int getFather(int x){ 30 return x==f[x] ? x : f[x]=getFather(f[x]); 31 } 32 33 void Union(int a, int b){ 34 int fa=getFather(a), fb=getFather(b); 35 if(fa!=fb){ 36 if(rank[fa]>rank[fb]){ 37 f[fb]=fa; 38 rank[fa]+=rank[fb]+1; 39 } 40 else{ 41 f[fa]=fb; 42 rank[fb]+=rank[fa]+1; 43 } 44 } 45 } 46 47 int main(){ 48 int t; 49 char cmd[3]; 50 scanf("%d", &t); 51 while(t--){ 52 scanf("%d%d", &n, &m); 53 init(); 54 while(m--){ 55 int u, v; 56 scanf("%s%d%d", cmd, &u, &v); 57 if(cmd[0]=='A'){ 58 int fu=getFather(u), fv=getFather(v); 59 if(fu==fv) 60 printf("In the same gang.\n"); 61 else if(fu==getFather(mark[v])) 62 printf("In different gangs.\n"); 63 else 64 printf("Not sure yet.\n"); 65 } 66 else{ 67 if(!mark[u] && !mark[v]){ 68 mark[u]=v; 69 mark[v]=u; 70 } 71 else if(!mark[u]){ 72 mark[u]=v; 73 Union(u, mark[v]); 74 } 75 else if(!mark[v]){ 76 mark[v]=u; 77 Union(v, mark[u]); 78 } 79 else { 80 Union(u, mark[v]); 81 Union(v, mark[u]); 82 } 83 } 84 } 85 } 86 return 0; 87 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3892571.html

總結(jié)

以上是生活随笔為你收集整理的poj1703Find them, Catch them（并查集以及路径压缩）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。