6 并查集 5题

sy360: 学校的班级个数（统计连通分量）中等

https://sunnywhy.com/sfbj/9/6/360

现有一个学校，学校中有若干个班级，每个班级中有若干个学生，每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级，学生B和学生C处于一个班级，那么我们称学生A和学生C也处于一个班级。

现已知学校中共 n 个学生（编号为从1到n），并给出 m 组学生关系（指定两个学生处于一个班级），问总共有多少个班级。

输入

第一行两个整数 $m、n(1\le n\le 100,1\le m\le 100)$，分别表示学生个数、学生关系个数；

接下来 m 行，每行两个整数 a 和 b $(1\le a\le n,1\le b\le n,a\ne b)$，表示编号为a的学生和编号为b的学生处于一个班级。

输出

输出一个整数，表示班级个数。

样例1

输入

5 3
4 2
1 3
2 5

输出

2

解释

编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级。

统计最后有多少个根

def find(x):
    if parent[x] != x: # 如果不是根结点，继续循环
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    parent[find(x)] = find(y)

n, m = map(int, input().split())
parent = list(range(n + 1))	# parent[i] == i，则说明元素i是该集合的根结点

for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)

classes = set(find(x) for x in range(1, n + 1))
print(len(classes))

sy361: 学校的班级人数（维护集合大小）中等

https://sunnywhy.com/sfbj/9/6/361

现有一个学校，学校中有若干个班级，每个班级中有若干个学生，每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级，学生B和学生C处于一个班级，那么我们称学生A和学生C也处于一个班级。

现已知学校中共 n 个学生（编号为从1到n），并给出 m 组学生关系（指定两个学生处于一个班级），问总共有多少个班级，并按降序给出每个班级的人数。

输入

第一行两个整数 $m、n(1\le n\le 100,1\le m\le 100)$，分别表示学生个数、学生关系个数；

接下来 m 行，每行两个整数 a 和 b $(1\le a\le n,1\le b\le n,a\ne b)$，表示编号为a的学生和编号为b的学生处于一个班级。

输出

第一行输出一个整数，表示班级个数；

第二行若干个整数，按降序给出每个班级的人数。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

5 3
4 2
1 3
2 5

输出

2
3 2

解释

编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级，人数分别是3和2。

核心： 合并时更新 size 数组。

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_x] = root_y
        size[root_y] += size[root_x]

n, m = map(int, input().split())
parent = list(range(n + 1))
size = [1] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)

#classes = [size[find(x)] for x in range(1, n + 1) if x == parent[x]]
classes = [size[x] for x in range(1, n + 1) if x == parent[x]]
print(len(classes))
print(' '.join(map(str, sorted(classes, reverse=True))))

sy362: 是否相同班级（连通） 中等

https://sunnywhy.com/sfbj/9/6/362

现有一个学校，学校中有若干个班级，每个班级中有若干个学生，每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级，学生B和学生C处于一个班级，那么我们称学生A和学生C也处于一个班级。

现已知学校中共 n 个学生（编号为从1到n），并给出 m 组学生关系（指定两个学生处于一个班级）。然后给出 k 个查询，每个查询询问两个学生是否在同一个班级。

输入

第一行两个整数 $n、m(1\le n\le {10}^5,1\le m\le {10}^5)$，分别表示学生个数、学生关系个数；

接下来 m 行，每行两个整数 a 和 b $ (1 \le a \le n, 1 \le b \le n, a \ne b)$，表示编号为a的学生和编号为b的学生处于一个班级。

然后一个整数 $k(1\le k\le {10}^3)$，表示查询个数；

接下来 k 行，每行两个整数 a 和 b $ (1 \le a \le n, 1 \le b \le n)$，表示询问编号为a的学生和编号为b的学生是否在同一个班级。

输出

每个查询输出一行，如果在同一个班级，那么输出Yes，否则输出No。

样例1

输入

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

输出

Yes
No

解释

编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此编号4和5的学生在同一个班级，编号1和2的学生不在同一个班级。

相同班级：直接判断 find(a) == find(b)。

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    parent[find(x)] = find(y)

n, m = map(int, input().split())
parent = list(range(n + 1))

for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)

k = int(input())
for _ in range(k):
    a, b = map(int, input().split())
    if find(a) == find(b):
        print('Yes')
    else:
        print('No')

sy363: 迷宫连通性 中等

https://sunnywhy.com/sfbj/9/6/363

现有一个迷宫，迷宫中有 n 个房间（编号为从1到n），房间与房间之间可能连通。如果房间A和房间B连通，房间B和房间C连通，那么我们称房间A和房间C也连通。给定 m 组连通关系（指定两个房间连通），问迷宫中的所有房间是否连通。

输入

第一行两个整数$n、m(1\le n\le 100,1\le m\le 100)$，分别表示房间个数、连通关系个数；

接下来行，每行两个整数 a 和 b $(1\le a\le n,1\le b\le n)$，表示编号为a的房间和编号为b的房间是连通的。

输出

如果所有房间连通，那么输出Yes，否则输出No。

样例1

输入

5 4
4 2
1 3
2 5
1 5

输出

Yes

解释

所有房间都连通，因此输出Yes。

样例2

输入

5 3
4 2
1 3
2 5

输出

No

解释

编号2、4、5的房间互相连通，编号1、3的房间互相连通，因此没有全部互相连通，输出No。

连通性：若最终集合个数为 1，则全连通。

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    parent[find(x)] = find(y)

n, m = map(int, input().split())
parent = list(range(n + 1))

for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)

sets = set(find(x) for x in range(1, n + 1))
if len(sets) == 1:
    print('Yes')
else:
    print('No')

sy364: 班级最高分 中等

https://sunnywhy.com/sfbj/9/6/364

现有一个学校，学校中有若干个班级，每个班级中有若干个学生，每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级，学生B和学生C处于一个班级，那么我们称学生A和学生C也处于一个班级。

现已知学校中共 n 个学生（编号为从1到n），每个学生有一个考试分数，再给出 m 组学生关系（指定两个学生处于一个班级），问总共有多少个班级，并按降序给出每个班级的最高考试分数。

输入

第一行两个整数 $n、m(1\le n\le 100,1\le m\le 100)$，分别表示学生个数、学生关系个数；

第二行为用空格隔开的 n 个整数（$0\le \mathrm{每}\mathrm{个}\mathrm{整}\mathrm{数}\le 100$），表示个学生的考试分数；

接下来 m 行，每行两个整数 a 和 b $(1\le a\le n,1\le b\le n)$，表示编号为a的学生和编号为b的学生处于一个班级。

输出

第一行输出一个整数，表示班级个数；

第二行若干个整数，按降序给出每个班级的最高考试分数。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

5 3
88 90 86 92 95
4 2
1 3
2 5

输出

2
95 88

解释

编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级，最高分数分别是编号1的学生的88分、编号5的学生的95分。

这个问题是一个典型的连通性问题。我们需要把具有关系的学生归到同一个集合（班级）中。并查集是处理这类问题最高效的数据结构。

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_x] = root_y
        
        # 每个班级的“根节点”位置上存储的 scores 永远是该班级所有成员中的最高分。
        scores[root_y] = max(scores[root_y], scores[root_x])

n, m = map(int, input().split())
parent = list(range(n + 1))
scores = list(map(int, input().split()))
scores.insert(0, 0)  # to make the scores 1-indexed

for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)

classes_scores = [scores[find(x)] for x in range(1, n + 1) if x == parent[x]]
print(len(classes_scores))
print(' '.join(map(str, sorted(classes_scores, reverse=True))))

复杂度分析

• 时间复杂度：O(m⋅α(n))，其中 α 是反阿克曼函数（几乎可以看作常数）。对于 n=100,m=100 的规模，性能绰绰有余

• 空间复杂度：O(n)，用于存储父节点数组和分数。