poj-1703

发表于   |   分类于 ，   |  

题目大意

　　http://poj.org/problem?id=1703

　　某个城市的罪犯分成两个帮派，给出一系列某两个罪犯是否是同一个帮派的信息，让你去推断某两个人是否是同一帮派。

题目分析

　　直接解感觉没思路，但是如果转换一下将每个罪犯属于帮派A，属于帮派B都作为数组的元素记录下来，那么

  • 当两个罪犯a和b属于相同帮派时，就讲a-A,b-A归在一起，将a-B,b-B归在一起。

  • 当两个罪犯a和b属于不同帮派时，就将a-B,b-A归在一起，将a-A,b-B归在一起。

    因此分析下来，有N个罪犯数组元素个数就是2N个，很自然的就用*并查集解就行了，注意最后判断如果罪犯a,b所对应的数组值相等则是同一个帮派，如果a跟b+N所对应的数组值相等，就不是一个帮派，否则的话就是不能确定。

    这个题如果拓展成3个帮派也是可以的，那么数组至少要有3*N元素，道理是一样的，只是判断稍微复杂一点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 200010
int par[MAX_SIZE], rank2[MAX_SIZE];
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank2[i] = 0;
    }
}
int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);//路径压缩
    }
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) {
        return;
    }
    if(rank2[x] < rank2[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if(rank2[x] == rank2[y]) {
           rank2[x]++;
        }
     }
    
}
bool same(int x, int y) {
    return find(x) == find(y);
}
void solve() {
    int T;
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        int N, K;
        scanf("%d%d", &N, &K);
        init(N * 2);
        
        for(int i = 0; i < K; i++) {
            int  x, y;
            char type;
            getchar();
            scanf("%c %d %d", &type, &x, &y);
            x = x - 1;
            y = y - 1;
            
            if(type == 'A') {
                if(same(x, y)) {
                    printf("In the same gang.\n");
                } else if (same(x, y + N)) {
                    printf("In different gangs.\n");
                } else {
                    printf("Not sure yet.\n");
                }
            } else { // 'D'
                unite(x, y + N);
                unite(x + N, y);
            }
        }
    }
}
int main() {
    solve();
    return 0;
}

时间复杂度待分析