首页 > 代码库 > poj1703(各种姿势)

poj1703(各种姿势)

题目链接:http://poj.org/problem?id=1703

 

题意:有n个人分别属于两个团伙,接下来m组形如 ch, x, y的数据,ch为“D"表示 x, y属于不同的团伙,ch为"A"表示询问x,y书否属于同一个团伙;

 

解法1:我们可以用jion(x, y)属于同一个团伙,jion(x+n, y)表示x属于第二个团伙,y属于第一个团伙,jion(x, y+n)表示x属于第一个团伙,y属于第二个团伙;

那么对于每组不同团伙的x, y我们只需要jion(x+n, y) ,jion(x, y+n)即可;查询时判断x,y或者x+n, y+n根节点是否相同即可,因为集合关系jion表示属于同一团伙,根节点相同则属于相同团伙,若x, y+n,或者x+n, y根节点相同则属于不同团伙,其余情况即为不能确定;

 

代码:

 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.\n");
56                 }else if(find(x)==find(y)||find(x+n)==find(y+n)){
57                     printf("In the same gang.\n");
58                 }else{
59                     printf("Not sure yet.\n");
60                 }
61             }
62         }
63     }
64     return 0;
65 }

 

方法2:用vis数组标记不同的集合,如:vis[x]=y,表示与x不同集合的点y;

用并查集合并属于同一类的点集;

代码:

 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.\n");
72                 }else if(find(x)==find(vis[y])){
73                     printf("In different gangs.\n");
74                 }else{
75                     printf("Not sure yet.\n");
76                 }
77             }
78         }
79     }
80     return 0;
81 }

 

方法3:

种类并查集,先区分能不能辨别的情况,然后只要考虑同和不同两种情况,可以用rank数组记录当前节点x与其根节点是否相同的信息,1表相同,0表不同;

 

代码:

 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.\n");
47                     }else{
48                         printf("In different gangs.\n");
49                     }
50                 }else{
51                     printf("Not sure yet.\n");
52                 }
53             }
54         }
55     }
56     return 0;
57 }

 

poj1703(各种姿势)