A Bug‘s Life

题目：A Bug’s Life

总结：带权并查集，vis[x]:x与x的根结点之间的关系,1表示两个相异，0表示两个相同。每次查找x和y的根结点的时候，通过路径压缩处理某个结点与某个结点的根结点之间的关系。
判断x和y的根结点是否一样，并且判断x与根结点和y与根结点的关系是否相同，如果相同则说明它们有一对是同的，

#include <stdio.h>
#include <string.h>
const int N = 100000;

int f[N],vis[N];
int n,m;

int find(int x){
    if(f[x] == x) return x;
    int root = f[x];
    f[x] = find(f[x]);
    vis[x] = vis[x]^vis[root];
    return f[x];
}

void init(int n){
    for(int i = 0;i <= n+1;i++){
        f[i] = i;
        vis[i] = 0;
    }
}
void solve(int k){
    int v = 0;
    scanf("%d%d",&n,&m);
    init(n);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(!v){
            int x_root = find(x);
            int y_root = find(y);
            if(x_root == y_root && vis[x] == vis[y]){
                v = 1;
            }else {
                f[x_root] = y_root;
                vis[x_root] = !(vis[x]^vis[y]);
            }
        }
    }
    if(v){
        printf("Scenario #%d:\nSuspicious bugs found!\n\n",k);
    }else{
        printf("Scenario #%d:\nNo suspicious bugs found!\n\n",k);
    }
}

int main(){
    int t;
    scanf("%d",&t);
    for(int i = 1;i <= t;i++){
       solve(i);
    }
    return 0;
}