并查集算法求解连接问题 - 1 <= n <= 100000

并查集算法求解连接问题 - 1 <= n <= 100000

问题描述:

给定一个包含 n 个节点的图，其中 1 <= n <= 100000。你需要处理一系列连接请求，每个请求包含两个节点 a 和 b，表示需要将节点 a 和 b 连接起来。输出每个请求的连接情况，即连接后两个节点所在的连通分量的大小。

输入:

第一行：一个整数 n，表示节点数量 (1 <= n <= 100000) 第二行至第 (n + 1) 行：每行包含两个整数 a 和 b，用空格分隔，表示一个连接请求 (1 <= a, b <= n)。

输出:

输出 n 行，每行一个整数，表示对应请求连接后两个节点所在的连通分量的大小。

示例输入:

5
1 2
3 4
2 4
1 5
3 5

示例输出:

0
0
1
1
1

提示:

本题可以使用并查集来解决。首先将每个节点的父节点初始化为自己，然后遍历每个询问，将 a 和 b 所在的集合合并起来，即将 a 所在集合的根节点的父节点指向 b 所在集合的根节点。最后遍历每个节点，输出该节点所在集合的大小减 1 即可。

代码示例 (Python):

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

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

n = int(input())
parent = [i for i in range(n + 1)]  # 初始化父节点
size = [1] * (n + 1)  # 初始化集合大小

for _ in range(n):
    a, b = map(int, input().split())
    union(a, b, parent, size)
    print(size[find(a, parent)] - 1)  # 输出连接后连通分量的大小

代码解释:

• find(x, parent) 函数用来查找节点 x 所在集合的根节点。
• union(x, y, parent, size) 函数用来将节点 x 和 y 所在的集合合并。
• parent 数组记录每个节点的父节点。
• size 数组记录每个集合的大小。

总结:

并查集是一种高效的数据结构，可以用于解决连接问题、连通性问题等。本题通过并查集算法，实现了对一系列连接请求的处理，并输出每个请求的连接情况。