算法课外思考题1118(团伙数量)

💡Author：信安2002钱泽枢(ShiQuLiZhi)

🚀欢迎访问我的作业合集：https://sxhthreo.github.io/categories/%E4%BD%9C%E4%B8%9A/

一、题目描述

在某个城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：

1. 我朋友的朋友是我的朋友；
2. 我敌人的敌人是我的朋友；

已知关于n个人的m条信息（即某2个人是朋友或者敌人），假设所有是朋友的人一定属于同一个团伙，请计算该城市最多有多少团伙？

二、算法思路

本题我们可以考虑并查集求解。

并查集的操作有：

• 将两个集合合并
• 询问两个元素是否在一个集合之中

并查集在近乎O(1)时间内快速支持两个操作。

基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

• 判断树根的方法：if(p[x] == x)
• 求x的集合编号的方法：while(p[x] != x) x = p[x];
• 合并两个集合的方法：p[x]是x的集合编号，p[y]是y的集合编号，p[x] = y

若两个人是朋友，则直接合并两集合即可；若两个人是敌人，我们考虑以下合并策略：

p[find(a + n)] = find(b);		// a + n 是反集
p[find(b + n)] = find(a);

在这里，a 和 a + n 其实是一个点，但是是两种不同的关系，连到 a 上的都是 a 的朋友，连到 a + n 上的都是 a 的敌人关系；

若 c 也是 a 的敌人，那么 c 也会连到 a + n 上，此时 b 和 c 就是朋友了，因为他们有共同的敌人a。

最后我们遍历所有集合，找到所有树根，即是最多的团伙数。

三、算法设计

在输入中，我们将每个人的信息进行以下格式的约定： F p q 或是 E p q，其中 $F$ 表示 $p$ 和 $q$ 是朋友，$E$ 表示 $p$ 和 $q$ 是敌人。

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

int getsum(int n, int m)
{
    int sum = 0;
    for (int i = 1; i <= 2 * n; i ++ ) p[i] = i;
    while (m--)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);	        // 当需要读取一个字母时,使用字符串进行读取
        if (*op == 'F') p[find(a)] = find(b);   // 是朋友
        else
        {
            p[find(a + n)] = find(b);
            p[find(b + n)] = find(a);
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        if(p[i] == i)
        {
            sum ++;
        }
    }
    return sum;
}

四、运行测试

本题是Acwing在线题库的784题：👉784. 强盗团伙👈

提交结果如下：

五、总结与讨论

本算法的时间性能取决于处理 $m$ 条信息的时间，时间复杂度是 $O(n)$ 的。

并查集是一种树形的数据结构，用于处理**不相交集的合并(union)及查询(find)**问题；通过并查集的思想，我们可以快速支持对合并集合和查询两个元素是否在一个集合内的操作。

在初始化并查集时我们初始化两倍于数据范围大小的并查集，超出数据范围部分称为反集，用来储存性质与并查集维护集合相反的集合，从而顺利实现两个人是敌人时集合的合并策略。

附：源代码

#include<iostream>
using namespace std;
const int N = 2010, M = 5010;

int p[N];

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

int getsum(int n, int m)
{
    int sum = 0;
    for (int i = 1; i <= 2 * n; i ++ ) p[i] = i;
    while (m--)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);	        // 当需要读取一个字母时,使用字符串进行读取
        if (*op == 'F') p[find(a)] = find(b);   // 是朋友
        else
        {
            p[find(a + n)] = find(b);
            p[find(b + n)] = find(a);
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        if(p[i] == i)
        {
            sum ++;
        }
    }
    return sum;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    cout << getsum(n, m);
    return 0;
}