POJ 1703: Find them, Catch them

概要

2種類の集合があって,2つの要素が異なる集合に属しているという情報と,2つの要素が同じ集合に属すかどうか問うクエリが来る.

解法

蟻本の練習問題と同様の考え方を用いる.要素vについて,集合Aに属している事象Avと,集合Bに属している事象Bvを用意し,それらをUnion-Find木で管理.aとbが異なる集合に属しているという情報が来れば,AaとBb,AbとBaを統合する.
クエリへの解答は,AaとAbが同じ集合に属しているのならaとbは同じ集合に属し,AaとBbが同じ集合に属しているならばaとbは違う集合に属す.どちらでもない場合は,その時点で判断ができない.

struct UnionFind{
    vector<int> parent, rank;
    UnionFind(int n) : parent(n, -1), rank(n, 0) { }
    int find(int x){
        if(parent[x] == -1) return x;
        else return (parent[x] = find(parent[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(rank[x] == rank[y]) rank[x]++;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

int N, M;
UnionFind uf(100010*2);

int main(){
    int T;
    scanf("%d", &T);
    for(--T; T>=0; --T){
        scanf("%d%d", &N, &M);
        fill(ALL(uf.parent), -1);
        fill(ALL(uf.rank), 0);
        for(int i = 0; i < M; ++i){
            char str[16];
            int a, b;
            scanf("%s%d%d", str, &a, &b);
            if(str[0] == 'D'){
                uf.unite(a * 2, b * 2 + 1);
                uf.unite(a * 2 + 1, b * 2);
            }
            else{
                if(uf.same(a * 2, b * 2)){
                    printf("In the same gang.\n");
                }
                else if(uf.same(a * 2, b * 2 + 1)){
                    printf("In different gangs.\n");
                }
                else{
                    printf("Not sure yet.\n");
                }
            }
        }
    }
    return 0;
}