POJ Union Find

1703. Find them, catch them

Tadu City里有两个黑帮团伙，现在知道城市里一共有N个罪犯，以及可以知道一些罪犯不属于一个黑帮，给出若干信息，其中一些信息是告诉某两个罪犯不属于一个黑帮，一些是询问两个罪犯是否是一个黑帮

输入，T个样例，每个样例一开始包括N和M，表示罪犯人数和信息数，之后每条信息有两种可能

• D a b 表示a和b属于不同黑帮
• A a b 询问a和b是否属于同一个黑帮

结果有三种

Not sure yet.
In different gangs.
In the same gang.

样例输入

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

样例输出

Not sure yet.
In different gangs.
In the same gang.

思路

用并查集来做，不过有一些技巧，如果想直接表达出两个集合的区分不太容易，这里将所有确定有关系的数放在一起，同时用另一个数组记录每个数和father的关系，0表示在一个帮派，1表示在不同帮派

一开始每个节点的father都是自己，关系也都是0

对于find，首先在带路径压缩的find后，所有节点都直接指向根节点，这时候可以根据点和fathe的关系，以及father和根节点的关系来确定该点和根节点的关系

对于merge，对点x和y，首先找到fx和fy，然后将fx指向fy，再更新fx和fy关系即可，这里x和y肯定是不同黑帮，所以看x和fx、y和fy的关系即可

在查询关系时，如果a和b不是同一个父亲，说明没有直接关系，是not sure，否则在find后这两点都直接和根相连，比较各自关系即可确定

综上，加上关系记录的并查集即可解题

#include <cstdio>

int father[100010], prev[100010];
int T, N, M;

int find(int num) {
    int f = father[num];
    if (num != father[num])
        father[num] = find(father[num]);
    prev[num] = (prev[f] == prev[num]) ? 0 : 1;
    return father[num];
}

int main() {
    scanf("%d", &T);
    for (int caserank = 1; caserank <= T; caserank++) {
        scanf("%d%d\n", &N, &M);
        for (int i = 1; i <= N; i++) {
            father[i] = i;
            prev[i] = 0;
        } 
        for (int i = 0; i < M; i++) {
            char c;
            int C, D;
            scanf("%c%d%d\n", &c, &C, &D);
            int fc = find(C), fd = find(D);
            if (c == 'D') {
                father[fc] = fd;
                prev[fc] = (prev[C] == prev[D]) ? 1 : 0;
            } else {
                if (fc != fd) printf("Not sure yet.\n");
                else if (prev[C] == prev[D]) printf("In the same gang.\n");
                else printf("In different gangs.\n");
            }
        }
    }
}