题意

教授提出猜想，所有虫子都是异性恋，给出交配情况，判断他的猜想是否正确（肯定不正确啊）

思路

这是一道并查集，没有错。但是呢，它是带有关系的并查集，显然可以用向量解决（同食物链那一题）。

但是这一题它的关系非常简单，杀鸡焉用牛刀，所以和POJ1703一样，可以手动处理虫子之间的关系逻辑，来解决这个问题。

也就是说，建立一个oppo数组，表示号与号性别不同，如果，说明此前尚未标记的对立点，那么就把此时的对立关系更新成。一共需要手写个逻辑。

最后POJ不能用万能头，切记。

solution

#include <cmath>
#include <cstdio>
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
int height[N];
int s[N];
int n;  // point numers
void init_set() {
    for (int i = 1; i <= n; ++i) s[i] = i, height[i] = 0;
}
int find_set(int x) {
    if (x != s[x]) s[x] = find_set(s[x]);  //路径压缩
    return s[x];
}
int find_set_circle(int x) {
    int r = x;
    while (s[r] != r) r = s[r];  //找到根节点
    s[x] = r;                    //把路径上的元素的集改为根节点
    return r;
}
void union_set(int x, int y) {
    x = find_set(x);
    y = find_set(y);
    if (height[x] == height[y])
        height[x] = height[x] + 1, s[y] = x;
    else if (height[x] < height[y])
        s[x] = y;
    else
        s[y] = x;
}
int main() {
    int T;
    int m;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        scanf("%d%d", &n, &m);
        init_set();
        int oppo[N] = {0};
        int a, b;
        bool flag = 1;
        while (m--) {
            scanf("%d%d", &a, &b);
            if (!flag) continue;
            if (oppo[a] && !oppo[b]) {
                union_set(oppo[a], b), oppo[b] = a;
            } else if (oppo[b] && !oppo[a]) {
                union_set(oppo[b], a), oppo[a] = b;
            } else if (oppo[a] && oppo[b]) {
                if (find_set(a) == find_set(b)) flag = 0;
                union_set(oppo[a], b), union_set(oppo[b], a);
            } else if (!oppo[a] && !oppo[b]) {
                oppo[a] = b, oppo[b] = a;
            }
        }
        if (t != 1) printf("\n");
        printf("Scenario #%d:\n", t);
        if (flag)
            printf("No suspicious bugs found!\n");
        else
            printf("Suspicious bugs found!\n");
    }
    return 0;
}