A Bug's Life

题意

题意很简单，就是给M组虫虫谁喜欢谁的关系，然后判断一下有没有同性恋的虫虫。
坑点：每一组数据输出之后还需要输出一个空行

分析

此题我以前用过二分图来做，这里用带权并查集做。如果存在这么一串关系，x->y->z(x喜欢y，y喜欢z),然后存储x,y,z到根结点的距离，dis[x] = 0,dis[y] = 1,dis[z] = 2,如果此刻又来了一个喜欢关系x->z，我们发现dis[x]%2 == dis[z]%2，所以x,z他们是同性关系，所以发现了同性恋虫虫
一句话：如果两个到根结点的距离是奇偶性相同的结点相爱，那么他两必定有一位是同性恋

AC代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn = 1e6+10;

int T,N,M;
int fa[maxn],dis[maxn];
void init(){
    for(int i = 1;i<=N;i++) {
        fa[i] = i;
        dis[i] = 0;
    }
}
int find(int x){
    if(x != fa[x]){
        int f = fa[x];
        fa[x] = find(fa[x]);
        dis[x] += dis[f];
    }
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
        dis[fx] = 1+dis[y]-dis[x];
    }
}
int main(){
    cin>>T;
    int kase = 1;
    while(T--){
        printf("Scenario #%d:\n",kase++);
        bool have = false;
        cin>>N>>M;
        init();
        while(M--){
            int x,y;
            scanf("%d%d",&x,&y);
            if(find(x) != find(y)){
                join(x,y);
            }else{
                if(dis[x]%2 == dis[y] %2){
                    have = true;
                }
            }
        }
        if(have) puts("Suspicious bugs found!");
        else puts("No suspicious bugs found!");
        puts("");
    }

    return 0;
}

ps:对同性恋无偏见，只是便于描述问题