1703:Find them, Catch them

keyword

union-find　C++

概要

2492:A Bug's Lifeと似た問題。
2つのチームがあり、aとbは所属が異なる、という情報とaとbの所属が同じかどうかというクエリが与えられる問題。
前と同じでUnion-Find使って実装。

int par[100005];

int getRoot(int x){
    if(abs(par[x]) == x) return x;
    return par[x] = getRoot(abs(par[x]))*(par[x]>0?1:-1);
}

bool isSame(int x, int y){
    return abs(getRoot(x)) == abs(getRoot(y));
}

void merge(int x,int y){
    if(isSame(x,y)) return ;
    int xx = getRoot(x), yy = getRoot(y);

    par[abs(xx)] = (xx>0)?(-yy):yy;

    return ;
}

int main(){
    int rept, n, m, i, x, y;
    char c;
    scanf("%d\n", &rept);

    while(rept--){
        scanf("%d%d\n",&n,&m);
        REP(i,n+1) par[i] = i;
        REP(i,m){
            scanf("%c %d %d\n",&c,&x,&y);
            if(c=='D'){
                merge(x,y);
            }
            else{
                if(!isSame(x,y)) printf("Not sure yet.\n");
                else if(getRoot(x)==getRoot(y)) printf("In the same gang.\n");
                else if(getRoot(x)==-getRoot(y)) printf("In different gangs.\n");
                //else printf("Not sure yet.\n");
            }
        }
    }

    return 0;
}