6 并查集 5题

sy360: 学校的班级个数（1）

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

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

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

输入

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

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

输出

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

样例1

输入

输出

解释

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

To solve this problem, you can use the concept of disjoint sets (also known as union-find). Each student is initially in their own set (or class). When a relationship between two students is given, you unite their sets. The number of disjoint sets at the end will be the number of classes.

Here is a step-by-step plan:

Initialize an array parent of size n+1 where parent[i] is initially i. This means each student is in their own class.
For each student relationship, unite their sets using the union operation.
Count the number of unique parents. This will be the number of classes.

Here is the Python code that implements this plan:

python

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))

This code reads the number of students and relationships from the input, initializes each student to be in their own class, unites the classes of each pair of students that have a relationship, and then counts and prints the number of unique classes.

sy361: 学校的班级人数（2）

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

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

输入

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

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

输出

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

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

样例1

输入

输出

2
3 2

解释

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

Here is a step-by-step plan:

Initialize an array parent of size n+1 where parent[i] is initially i. This means each student is in their own class.
Initialize an array size of size n+1 where size[i] is initially 1. This means each class initially has one student.
For each student relationship, unite their sets using the union operation and update the size of the new set.
Count the number of unique parents. This will be the number of classes.
Print the sizes of the classes in descending order.

Here is the Python code that implements this plan:

python

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))))

This code reads the number of students and relationships from the input, initializes each student to be in their own class, unites the classes of each pair of students that have a relationship, counts and prints the number of unique classes, and prints the sizes of the classes in descending order.

sy362: 是否相同班级

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

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

输入

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

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

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

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

输出

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

样例1

输入

输出

Yes
No

解释

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

To solve this problem, you can use the concept of disjoint sets (also known as union-find). Each student is initially in their own set (or class). When a relationship between two students is given, you unite their sets. For each query, you check if the two students are in the same set.

Here is a step-by-step plan:

Initialize an array parent of size n+1 where parent[i] is initially i. This means each student is in their own class.
For each student relationship, unite their sets using the union operation.
For each query, check if the two students are in the same set using the find operation.

Here is the Python code that implements this plan:

python

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 \leq n \leq 100, 1 \leq m \leq 100)$ ，分别表示房间个数、连通关系个数；

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

输出

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

样例1

输入

输出

Yes

解释

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

样例2

输入

输出

No

解释

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

To solve this problem, you can use the concept of disjoint sets (also known as union-find). Each room is initially in its own set. When a connection between two rooms is given, you unite their sets. If at the end there is only one set, then all rooms are connected.

Here is a step-by-step plan:

Initialize an array parent of size n+1 where parent[i] is initially i. This means each room is in its own set.
For each connection, unite their sets using the union operation.
Check if all rooms are in the same set.

Here is the Python code that implements this plan:

python

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')

This code reads the number of rooms and connections from the input, initializes each room to be in its own set, unites the sets of each pair of rooms that have a connection, and then checks and prints whether all rooms are in the same set.

sy364: 班级最高分

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

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

输入

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

第二行为用空格隔开的 n 个整数（ $0 \leq 每个整数 \leq 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分。

Here is a step-by-step plan:

Initialize an array parent of size n+1 where parent[i] is initially i. This means each student is in their own class.
Initialize an array scores of size n+1 to store the scores of each student.
For each student relationship, unite their sets using the union operation.
For each class, find the maximum score.
Count the number of unique parents. This will be the number of classes.
Print the maximum scores of the classes in descending order.

Here is the Python code that implements this plan:

python

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[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))))

This code reads the number of students and relationships from the input, initializes each student to be in their own class, unites the classes of each pair of students that have a relationship, finds the maximum score for each class, counts and prints the number of unique classes, and prints the maximum scores of the classes in descending order.

6 并查集 5题 ​

sy360: 学校的班级个数（1） ​

sy361: 学校的班级人数（2） ​

sy362: 是否相同班级 ​

sy363: 迷宫连通性 ​

sy364: 班级最高分 ​

6 并查集 5题

sy360: 学校的班级个数（1）

sy361: 学校的班级人数（2）

sy362: 是否相同班级

sy363: 迷宫连通性

sy364: 班级最高分