poj 2492 A Bug's Life 【并查集拓展】

Description

Input

Output

Sample Input

2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

Sample Output

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

Hint

题意：找是不是同性恋的两条虫子。

参考：http://www.cnblogs.com/dongsheng/archive/2012/08/08/2627917.html

代码：

#include <cstdio>
#include <cstring>
const int M = 2050;

int fat[M], ral[M];

int f(int x){
    if(fat[x] != x){
        int root = fat[x];
        fat[x] = f(fat[x]);
        ral[x] = (ral[x]+ral[root])%2;
    }
    return fat[x];
}

int main(){
    int t, v = 1, n, m;
    scanf("%d", &t);
    while(t --){
        scanf("%d%d", &n, &m);
        int i, a, b;
        for(i = 1; i < M; i++) fat[i] = i;
        memset(ral, 0, sizeof(ral));
        int flag = 0;
        while(m --){
            scanf("%d%d", &a, &b);
            if(flag) continue;
            else{
                int x = f(a); int y = f(b);
                if(x == y){
                    if(ral[a] == ral[b]) flag = 1;
                }
                else{
                    fat[x] = y;
                    ral[x] = (ral[a]+ral[b]+1)%2;
                }
            }
        }
        printf("Scenario #%d:\n", v++);
       if(flag)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");
        if(t)
            printf("\n");
    }
    return 0;
}

poj 2492 A Bug's Life 【并查集拓展】

原文：http://blog.csdn.net/shengweisong/article/details/41746857