2492:A Bug's Life

keyword

Union-Find　C++

概要

n匹の番号が振られた虫と、交配した虫のペアの情報が与えられる。このとき、両性の虫が確実に存在するかどうかを求める問題。
自力では思いつかなかったがI先生にUnion-Findで一発じゃん、と言われる。親の番号に符号をつけるなり否定をとるなりすれば良いようだった。実装に手間取ったけどAC。

int ps[2002];
bool found;

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

void merge(int x, int y){
    if(found) return ;
    int xx = getRoot(x), yy = getRoot(y);
    if(xx == yy) found = true;
    ps[abs(xx)] = (xx>0)?(-yy):yy;
    return ;
}

int main(){
    int i, j, rept, n, m, x, y;
    scanf("%d",&rept);
    LOOP(rept){
        scanf("%d%d",&n,&m);
        found = false;
        REPONE(i,n)ps[i]=i;
        REP(i,m){
            scanf("%d%d",&x,&y);
            merge(x,y);
            //REPONE(j,n)printf("%d, ",ps[j]);printf("\n");
        }
        printf("Scenario #%d:\n", loopCount);
        if(found) printf("Suspicious bugs found!\n");
        else printf("No suspicious bugs found!\n");
        if(loopCount < rept) printf("\n");
    }
    return 0;
}