AcWing 837. 连通块中点的数量

题目描述

---

分析：

本题是对并查集的变形应用，如果对并查集的基本概念了解不够透彻的可以看复习一下：并查集的递推和递归写法。先看 Q1 操作，就是并查集那查找的基本操作，不再赘述。本题的变形之处在于给集合附加了“大小”属性，即在维护 father 数组的同时也要维护一个 ssize 数组，其中 ssize[根结点] 存储了该根结点下集合内元素的数量，而 ssize 的初始化也比较好理解，即我们之前提到的：初始时每个元素都是独立的一个集合，所以ssize[i] = 1$(1\le i\le N)$。对于 Q2 操作，我想思路已经很清楚了，直接查询给定的根结点信息并输出 ssize[father[input]] 即可。但还有另外一点就是 C 操作（合并两个集合）时，合并后的连通块大小该如何更新呢？假设我们需要合并两连通块，那么最重要的就是要找到两连通块的根结点，设为 findFather(a) findFather(a)。然后将 findFather(a) 连通块大小加到 findFather(a) 的连通块上即可。

---

代码(C++)

#include 

using namespace std;

const int N = 100010;
int father[N], ssize[N];

int findFather(int x)
{
    if (x == father[x]) return x; // 直到找到根结点
    else
    {
        int F = findFather(father[x]); // 等式右边找到根结点后开始回溯
        father[x] = F; // 路径上的每个结点的父结点都设置为根结点
        return F;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++)
    {
        father[i] = i;
        ssize[i] = 1; // 初始化，使所有连通块的大小都为 1
    }
    
    while (m --)
    {
        string op;
        int a, b;
        cin >> op;
        
        if (op == "C")
        {
            cin >> a >> b;
            if (findFather(a) != findFather(b))
            {
                /*这里是易错点，如果没有题前将a b集合的根结点取出来的操作
                    例如 a = findFather(a) b = findFather(b)，
                    那就一定要按照先更改连通块大小再进行集合合并的操作！！
                    若没有取出根结点又颠倒操作，则会导致更改连通块大小时根结点的重叠
                    导致答案出错
                */
                // 接入 b 的集合后，b 应该加上 a 集合的连通块的大小
                ssize[findFather(b)] += ssize[findFather(a)];
                // 将 a 为根结点的集合接到 b 为根结点的集合下
                father[findFather(a)] = findFather(b); 
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (findFather(a) == findFather(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << ssize[findFather(a)] << endl;
        }
        
    }
}
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

---