poj1703(各种姿势)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define MAXN (100000+10)  //***MAXN后面做下标时MAXN*2，要加括号，不然会越界！！run time error！！！
 5 using namespace std;
 6 
 7 int pre[MAXN*2], rank[MAXN*2]; //***rank用来区分树的高度，但其不存储树的具体高度
 8 
 9 int find(int x){    
10     int r = x;
11     while(pre[r]!=r){
12         r = pre[r];
13     }
14     int i = x;      //****路径压缩
15     while(pre[i]!=r){
16         int gg = pre[i];
17         pre[i] = r;
18         i = gg;
19     }
20     return r;
21 }
22 
23 void jion(int x, int y){
24     int xx = find(x);
25     int yy = find(y);
26     if(rank[xx]>rank[yy]){   //***启发式合并，就是把矮的树合并到高的树地下，把合并时间从0(n)降到o(logn)
27         pre[yy] = xx;
28     }else{
29         pre[xx] = yy;
30         if(rank[xx] == rank[yy]){ //**若树的标记高度一样，那么给合并后作为父亲的树rank+1，以区分树的高度
31             rank[xx]++;
32         }
33     }
34 }
35 
36 int main(void){
37     int t;
38     scanf("%d", &t);
39     while(t--){
40         int n, m;
41         scanf("%d%d", &n, &m);
42         for(int i=1; i<=2*n; i++){
43             pre[i] = i;
44             rank[i] = 0;
45         }
46         while(m--){
47             char ch[2];
48             int x, y;
49             scanf("%s%d%d", ch, &x, &y);
50             if(ch[0]==‘D‘){
51                 jion(x, y+n);
52                 jion(x+n, y);
53             }else{
54                 if(find(y+n)==find(x)||find(x+n)==find(y)){
55                     printf("In different gangs.
");
56                 }else if(find(x)==find(y)||find(x+n)==find(y+n)){
57                     printf("In the same gang.
");
58                 }else{
59                     printf("Not sure yet.
");
60                 }
61             }
62         }
63     }
64     return 0;
65 }

 1 #include <iostream>
 2 #include <stdio.h>
 3 #define MAXN 100010
 4 using namespace std;
 5 
 6 int pre[MAXN], vis[MAXN], rank[MAXN]; //***vis标记不同集合的编号，rank区分树高
 7 //***vis[x]=y，表示记录x与y不同集合，相当于无向图，所以需双向标记
 8 
 9 /*int find(int x){  //**400+ms
10     int r = x;
11     while(pre[r]!=r){
12         r = pre[r];
13     }
14     int i = x;
15     while(i!=r){
16         int gg = pre[i];
17         pre[i] = r;
18         i = gg;
19     }
20     return r;
21 }*/
22 
23 int find(int x){ //**306ms (再加启发式合并=282ms)
24     return pre[x]==x ? x : pre[x] = find(pre[x]);
25 }
26 
27 void jion(int x, int y){
28     int xx = find(x);
29     int yy = find(y);
30     if(rank[xx] > rank[yy]){
31         pre[yy] = xx;
32     }else{
33         pre[xx] = yy;
34         if(rank[xx] == rank[yy]){
35             rank[yy]++;
36         }
37     }
38 }
39 
40 int main(void){
41     int t;
42     scanf("%d", &t);
43     while(t--){
44         int n, m;
45         scanf("%d%d", &n, &m);
46         for(int i=1; i<=n; i++){
47             pre[i] = i;
48             vis[i] = 0;
49             rank[i] = 0;
50         }
51         while(m--){
52             char ch[2];
53             int x, y;
54             scanf("%s%d%d", ch, &x, &y);
55             if(ch[0]==‘D‘){
56                 if(vis[x]==0 && vis[y]==0){  //**x, y都没出现过
57                     vis[x] = y;
58                     vis[y] = x;
59                 }else if(vis[x]==0){ //**x没出现过
60                     vis[x] = y;
61                     jion(x, vis[y]);
62                 }else if(vis[y]==0){ //**y没出现过
63                     vis[y] = x;
64                     jion(y, vis[x]);
65                 }else{               //**都出现过
66                     jion(x, vis[y]);
67                     jion(y, vis[x]);
68                 }
69             }else{
70                 if(find(x)==find(y)){
71                     printf("In the same gang.
");
72                 }else if(find(x)==find(vis[y])){
73                     printf("In different gangs.
");
74                 }else{
75                     printf("Not sure yet.
");
76                 }
77             }
78         }
79     }
80     return 0;
81 }

 1 #include <iostream>
 2 #include <stdio.h>
 3 #define MAXN 100010
 4 using namespace std;
 5 
 6 int pre[MAXN], rank[MAXN]; //**rank储存x与x的根节点是否相同的信息，1表相同，0表不同
 7 
 8 int find(int x){
 9     if(x==pre[x]){
10         return pre[x];
11     }
12     int xx = pre[x];
13     pre[x] = find(pre[x]);
14     rank[x] = (rank[x] + rank[xx])&1; //**压缩路径，x的根节点改变了，rank[x]也要改变
15     return pre[x];
16 }
17 
18 void jion(int x, int y){
19     int xx = find(x);
20     int yy = find(y);
21     if(xx!=yy){
22         pre[yy] = xx;
23         rank[yy] = (rank[x] + rank[y] + 1)&1; //**合并只需改变yy之前的rank值
24     }
25 }
26 
27 int main(void){
28     int t;
29     scanf("%d", &t);
30     while(t--){
31         int n, m;
32         scanf("%d%d", &n, &m);
33         for(int i=1; i<=n; i++){
34             pre[i] = i;
35             rank[i] = 0;
36         }
37         while(m--){
38             char ch[2];
39             int x, y;
40             scanf("%s%d%d", ch, &x, &y);
41             if(ch[0]==‘D‘){
42                 jion(x, y);
43             }else{
44                 if(find(x)==find(y)){
45                     if(rank[x]==rank[y]){
46                         printf("In the same gang.
");
47                     }else{
48                         printf("In different gangs.
");
49                     }
50                 }else{
51                     printf("Not sure yet.
");
52                 }
53             }
54         }
55     }
56     return 0;
57 }