poj1703Find them, Catch them（并查集以及路徑壓縮）

 1 /*
 2    題目大意：有兩個不同的黑幫，開始的時候不清楚每個人是屬于哪個的！
 3   執行兩個操作
 4   A a, b回答a, b兩個人是否在同一幫派，或者不確定
 5   D a, b表示a, b兩個人不在同一個幫派
 6 
 7   思路：利用并查集將相同幫派的人合并到一起！
 8            a ,b 不在同一個城市，那么 a, 和mark[b]就在同一個城市，
 9            b 和 mark[a]就在同一個城市！
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]不在同一個黑幫 
18 int rank[M];//為不同的集合的父親節點記錄其孩子機節點個數，在合并集合的時候，將
19 int n, m;   //rank 值小的集合連接到 rank 值大的集合上去！ 這樣在路徑壓縮的時候省去不少時間 
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 }

轉載于:https://www.cnblogs.com/hujunzheng/p/3892571.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531801.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531801.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531801.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！