并查集

在讲并查集之前，我们先思考一个问题，假设幼儿园小班有六个小朋友，分别为小a，小b，小c，小d，小e，小f，
但并不是每个人都是朋友， 我们规定朋友的朋友也是朋友，例如小a和小b是朋友，小b和小c也是朋友，那么小c和
小a同样也是朋友。现在要求一共有几个朋友圈。 已知小a和小b是朋友，小d和小e是朋友，小e和小f是朋友。我们很
容易能够确认小a和小b是一个朋友圈，小d，小e以及小f是一个朋友圈，而小c自己一个人一个朋友圈。

因为人数很少，我们能够很轻易地判断有几个朋友圈，但当人数很多的时候呢，我们不能每个都去遍历，去数有多少
个朋友圈。这就需要我们本次的知识——并查集。

并查集我们通过构建树状结构来实现，在这里我们分析上面的例子，首先在条件未知的情况下，我们让每个人都自己
一个人为一个朋友圈，如下图：

朋友圈情况

在初始情况下，每个小朋友自己一个人为一个朋友圈，在上面我们说了，并查集通过树状结构实现，所以就需要根节点，
初始状态下，根结点就是他们本身。现在我们接入第一个条件，即小a和小b是朋友，能够确认的是把小a和小b连接起来，
但问题是如何连接——答案是分别寻找他们的根节点，然后把他们的根节点连接起来，并且把其中一个根节点当作另一个根节点的父节点.
这也即使并查集的思想。所以这里我们要把小a和小b的根节点起来，并且把小b的根节点作为小a根节点新的子节点，如下图：

朋友圈情况

看到这里的时候，有人会想，随着人数增多，如何找到他们的根节点呢？这里就需要引进一个find()函数来寻找他们的根节点，
而find()的目的就是为了查询他们的根节点，具体如下：

1
2
3
4
5
6
int find(int x)
    {
        if (pre[x] == x)
            return x;
        return find(pre[x]);
    }

上面的find()的代码，如果pre[x]的根节点等于它本身，则返回它本身，如果不是，则返回find(pre[x])，通过
继续递归函数，获得最终的根节点。

查找根节点有find()函数，那么把两个节点连接在一起，同样有一个合并函数merge(),find()函数和merge()函数
是并查集具备的两大操作，merge()函数如下：

1
2
3
4
void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

merge()函数很简单，只需要把一个节点的根节点等于另一个根节点即可。

所有的关系都引入之后，朋友圈状况如下：

朋友圈情况

上面就是并查集的主要思想，下面看一个例子：

题目描述

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，
那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果 M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，
否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

分析: 很明显这就是一个并查集的问题，并且与我们的例子很相似，只不过这里使用矩阵来表示谁和谁是朋友，具体代码
如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>

using namespace std;

// 初始化并查集，每个元素自己就是一个集合
vector<int> initUnionFind(int n) {
    vector<int> parent(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 初始时，每个节点的父节点是自己
    }
    return parent;
}

// 查找元素x的根节点
int findRoot(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = findRoot(parent, parent[x]); // 路径压缩，直接让x的父节点变为根节点
    }
    return parent[x];
}

// 合并元素x和元素y所在的集合
void unite(vector<int>& parent, int x, int y) {
    int rootX = findRoot(parent, x);
    int rootY = findRoot(parent, y);
    if (rootX != rootY) {
        parent[rootX] = rootY; // 将x的根节点的父节点设为y的根节点，实现集合合并
    }
}

// 计算并查集中集合的个数
int countCircles(vector<int>& parent, int n) {
    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (findRoot(parent, i) == i) {
            ++count; // 如果i是根节点，说明它是一个独立的集合
        }
    }
    return count;
}

// 主函数，计算朋友圈总数
int findCircleNum(vector<vector<int>>& M) {
    int N = M.size();
    vector<int> parent = initUnionFind(N); // 初始化并查集

    // 遍历矩阵M，合并朋友关系对应的节点
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (M[i][j] == 1) {
                unite(parent, i, j); // 如果i和j是朋友，合并他们所在的集合
            }
        }
    }

    // 计算并查集中集合的个数，即朋友圈的总数
    return countCircles(parent, N);
}

int main() {
    int N;
    cin >> N;

    vector<vector<int>> M(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> M[i][j];
        }
    }

    int numCircles = findCircleNum(M);
    cout << numCircles << endl;

    return 0;
}

关于并查集的知识就到这里，有什么问题请打在评论区，谢谢！