C++ 并查集算法：判断朋友关系

题目描述

朋友关系具有传递性：如果 'a' 和 'b' 是朋友、'b' 和 'c' 是朋友，那么 'a' 和 'c' 也是朋友。 'n' 个人一开始两两都不是朋友，接下来的时间里，他们中的一些人会不断成为朋友。两个人一旦成为朋友，他们就永远是朋友了。 现在有 'm' 个操作或询问，每个操作或询问用 't,i,j' 表示：

• 't = 0'，表示 'i' 和 'j' 成为了朋友。
• 't = 1'，表示询问 'i' 和 'j' 是否为朋友。

输入格式

从标准输入读入数据。 输入共 'm+1' 行。 第一行两个整数 'n, m' （'1 ≤ n,m ≤ 1000'）。 接下来 'm' 行，每行三个整数 't,i,j' （'t∈ {0,1}'，'1 ≤ i, j ≤ n'）表示一个操作或询问。

输出格式

输出到标准输出。 对于每个询问，输出一行，如果 'i' 和 'j' 是朋友，则输出 '1'；否则输出 '0' 。

样例 #1

样例输入 #1

5 5
0 1 4
1 5 5
1 4 1
0 5 1
1 3 2

样例输出 #1

1
1
0

C++ 代码实现

#include <iostream>
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 n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 0) p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) puts("1");
            else puts("0");
        }
    }

    return 0;
}

代码解析

1. 并查集数组： 'p[N]' 数组用来存储每个节点的父节点，初始状态下每个节点的父节点是自己。
2. find 函数： 用于查找节点的根节点，并进行路径压缩优化，使得后续查询效率更高。
3. 合并操作： 当 't = 0' 时，将 'a' 和 'b' 合并到同一个集合中，即设置 'a' 的根节点为 'b' 的根节点。
4. 查询操作： 当 't = 1' 时，判断 'a' 和 'b' 是否在同一个集合中，即判断它们的根节点是否相同。

并查集算法的优势

并查集算法在处理动态集合的连接和查询操作时，具有以下优势：

• 时间复杂度低： 经过路径压缩优化后，并查集操作的平均时间复杂度接近常数级别，非常高效。
• 代码简洁： 实现并查集算法的代码相对简洁，易于理解和维护。

总结

本文介绍了并查集算法的基本原理和实现方法，并通过代码示例展示了如何使用并查集来解决判断朋友关系问题。并查集是一种强大的数据结构，在很多算法问题中都有广泛的应用。

希望本文能够帮助你更好地理解和掌握并查集算法，并将其应用到实际问题中。