1.A Bug’s Life

种类并查集

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2010;

int p[N * 2]; // 假定1 ~ n表示雄性，n+1 ~ 2*n表示雌性
int t, n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x != y) p[x] = y;
}

int main()
{
    scanf("%d", &t);

    for (int i = 1; i <= t ; i ++ )
    {
        int flag = 0;
        memset(p, 0, sizeof p);

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

        for (int j = 1; j <= n * 2; j ++ ) p[j] = j;

        while (m -- )
        {
            int a, b;
            scanf("%d%d", &a, &b);

            int fa = find(a), fb = find(b);
            if (fa == fb) flag = 1; // 同性恋，发现假设不成立，这里不能break,要等到数据输完
            else // a和b不同性别，有两种情况
            {
                merge(a + n, b);
                merge(a, b + n);
            }
        }

        printf("Scenario #%d:\n",i);
        if(flag == 1) printf("Suspicious bugs found!\n\n");
        else printf("No suspicious bugs found!\n\n");
    }
    return 0;
}

2.How Many Tables

查询连通块的个数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        memset(p, 0, sizeof p);

        int n, m;
        cin >> n >> m;

        for (int i = 1; i <= n; i ++ ) p[i] = i;

        while (m -- )
        {
            int a, b;
            cin >> a >> b;
            int fa = find(a), fb = find(b);
            if (fa != fb) p[fa] = fb;
        }

        int res = 0;
        for (int i = 1; i <= n; i ++ )
            if (p[i] == i)
                res ++ ;
        cout << res << endl;
    }
    return 0;
}

3.小希的迷宫

判断连通块中是否存在环

//flag[i]数组标记i是否出现，FLAG标记是否有环，sum记录集合的个数
#include <iostream>
#include <cstdio>

const int N = 100010;

int flag[N], p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b)
{
    int fa = find(a), fb = find(b);
    p[fa] = fb;
}

int main()
{
    int a, b;
    while (~scanf("%d%d",&a,&b))
    {

        if (a == -1 && b == -1) break;

        for (int i = 0; i <= N; i ++ ) flag[i] = 0, p[i] = i;

        int FLAG = 0;
        while (1)
        {
            if (a == 0 && b == 0) break;

            if (find(a) == find(b)) FLAG = 1; // 在建立两点之间的边时应查询它们的根节点是否相同，如果相同就是有环的，否则无环
            merge(a,b);

            flag[a] = 1, flag[b] = 1; // 建立完边之后打上标记 
            scanf("%d%d", &a, &b);   // 先对第一次输入的数据判断，所以输入放在最后 
        }

        if (FLAG == 1) printf("No\n");
        else
        {
            int sum = 0;
            for (int i = 0; i <= N; i ++ )
                if(flag[i] && p[i] == i)
                    sum ++ ;

            if (sum > 1) printf("No\n");
            else printf("Yes\n");
        }
    }
    return 0;
}

4.How Many Answers Are Wrong

并查集+前缀和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int p[N], d[N]; // d[x]存x点到根节点的距离
int n, m;

int find(int x)
{
    if (p[x] != x) 
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    while (cin >> n >> m)
    {
        memset(p, 0, sizeof p);
        memset(d, 0, sizeof d);
        for (int i = 1; i <= n; i ++ ) p[i] = i;

        int res = 0;
        while (m -- )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            a -- ;
            int fa = find(a), fb = find(b);
            if (fa != fb)
            {
                p[fb] = fa;
                d[fb] = d[a] - d[b] + c;
            }
            else if (d[b] - d[a] != c)
                res ++ ;
        }
        cout << res << endl;
    }
    return 0;
}

5.食物链

维护到根节点距离的并查集

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N]; // d[]存储到根节点的距离
// 到根节点的距离(mod 3 余 0)表示与根节点同类
// 到根节点的距离(mod 3 余 1)表示吃根节点
// 到根节点的距离(mod 3 余 2)表示被根节点吃

int find(int x)  // 并查集
{
    if (p[x] != x)
    {
        int t = find(p[x]); // 先让当前点的父节点落位
        d[x] += d[p[x]]; // x到根节点的距离 = x到原来父节点的距离(d[x]) + 原来父节点到最终父节点的距离(d[p(x)])
        p[x] = t; // 更新当前点的父节点
    }
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int res = 0;
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if (x > n || y > n) res ++ ; // 编号越界是假话
        else
        {
            int fx = find(x), fy = find(y);
            if (t == 1) // x,y同类
            {
                if (fx == fy && (d[x] - d[y]) % 3) res ++ ; // 祖宗节点和距离表示要相同才能说明与前面的陈述不冲突
                else if (fx != fy)
                {
                    p[fx] = fy;
                    d[fx] = d[y] - d[x]; // (d[x] + d[fx]) mod 3 要与 d[y] mod 3 的结果相同
                }
            } 
            else // x吃y 
            {
                if (fx == fy && (d[x] - d[y] - 1) % 3) res ++ ; // x吃y说明d[x] mod 3 比 d[y] mod 3 大1
                else if (fx != fy)
                {
                    p[fx] = fy;
                    d[fx] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n", res);

    return 0;
}

6.亲戚

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010;

int n, m, q, p[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (find(a) != find(b)) p[find(a)] = find(b);
    }
    scanf("%d", &q);
    while (q -- )
    {
        int c, d;
        scanf("%d%d", &c, &d);
        if (find(c) == find(d)) puts("Yes");
        else puts("No");
    }
    return 0;
}