poj 2492 A Bug's Life 二分图染色 || 种类并查集

题目链接

题意

有一种\(bug\)，所有的交往只在异性间发生。现给出所有的交往列表，问是否有可疑的\(bug\)（进行同性交往）。

思路

法一：种类并查集

参考：https://www.2cto.com/kf/201310/249052.html

对于每一个集合中的元素，用一个数组\(rank\)记录它和它的祖先性别是否相同，\(0\)为相同，\(1\)为不同。每个祖先的\(rank\)值为\(0\).

路径压缩时：rank[x] = rank[prev_fa]^rank[x];

因为是递归进行的路径压缩，所以更新\(x\)的\(rank\)时，它之前父亲的\(rank\)值已经被更新过了，因为\(0\)表示相同，\(1\)表示不同，所以若\(rank[x]=0\)，意味着\(x\)和它之前父亲的性别一样，其和新父亲的关系 和 原父亲与新父亲的关系 相同；若\(rank[x]=1\)，意味着\(x\)和它之前父亲的性别不同，其和新父亲的关系 和 原父亲与新父亲的关系 不同。其实就是异或。

合并时：rank[xx]=!(rank[x]^rank[y]);

这里\(x\)的父亲为\(xx\)，\(y\)的父亲为\(yy\). 若\(rank[x]==rank[y]\)，因为\(x\)和\(y\)性别不同，而\(x\)和\(xx\)性别的关系与\(y\)和\(yy\)性别的关系相同，所以\(xx\)和\(yy\)性别不同；若\(rank[x]!=rank[y]\)，因为\(x\)和\(y\)性别不同，而\(x\)和\(xx\)性别的关系与\(y\)和\(yy\)性别的关系也不同，所以\(xx\)和\(yy\)性别相同。其实就是同或。

法二：判断二分图

也可以用并查集写~

Code

Ver. 1

#include <stdio.h>

#include <iostream>

#define maxn 2010

using namespace std;

typedef long long LL;

int fa[maxn], rk[maxn], sz[maxn];

int find(int x) {

    if (fa[x] == x) return x;

    int tmp = fa[x];

    fa[x] = find(fa[x]);

    rk[x] = rk[tmp] ^ rk[x];

    return fa[x];

}

int kas;

void work() {

    printf("Scenario #%d:\n", ++kas);

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) sz[i] = 1, fa[i] = i, rk[i] = 0;

    bool flag = false;

    for (int i = 0; i < m; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        if (flag) continue;

        int xx = find(x), yy = find(y);

        if (xx == yy) {

            if (rk[x] == rk[y]) flag = true;

        }

        else {

            if (sz[xx] > sz[yy]) swap(xx, yy), swap(x, y);

            fa[xx] = yy; rk[xx] = !(rk[x] ^ rk[y]); sz[yy] += sz[xx];

        }

    }

    if (flag) printf("Suspicious bugs found!\n\n");

    else printf("No suspicious bugs found!\n\n");

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) work();

    return 0;

}

Ver.2

#include <stdio.h>

#include <iostream>

#define maxn 4010

using namespace std;

typedef long long LL;

int fa[maxn], rk[maxn], sz[maxn];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void unionn(int x, int y) {

    x = find(x), y = find(y);

    if (sz[x] > sz[y]) swap(x, y);

    fa[x] = y, sz[y] += sz[x];

}

int kas;

void work() {

    printf("Scenario #%d:\n", ++kas);

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= 2*n; ++i) sz[i] = 1, fa[i] = i;

    for (int i = 0; i < m; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        unionn(x, y+n), unionn(y, x+n);

    }

    bool flag = false;

    for (int i = 1; i <= n; ++i) if (find(i)==find(i+n)) { flag = true; break; }

    if (flag) printf("Suspicious bugs found!\n\n");

    else printf("No suspicious bugs found!\n\n");

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) work();

    return 0;

}