并查集#

原理和板子#

并查集（Union-Find）是一种用于处理不相交集合合并与查询的数据结构，常用于判断连通性、检测环、求解最小生成树等场景。它主要支持两种操作：

查找（find）：确定某个元素属于哪个集合，通常返回集合的“根”元素（代表元）。
合并（union）：将两个不同的集合合并为一个集合。

1
def find(p, x):
2
    if p[x] != x:
3
        p[x] = find(p, p[x])   # 路径压缩
4
    return p[x]

p 数组存储每个元素的父节点，根节点的父节点为自身。
递归查找根节点，同时将路径上的节点直接指向根，加速后续查找。

1
def union(p, rank, x, y):
2
    rx, ry = find(p, x), find(p, y)
3
    if rx == ry:
4
        return False          # 已属同一集合
5
    # 按秩合并：将秩较小的树接到秩较大的树下
6
    if rank[rx] < rank[ry]:
7
        p[rx] = ry
8
    elif rank[rx] > rank[ry]:
9
        p[ry] = rx
10
    else:
11
        p[ry] = rx
12
        rank[rx] += 1
13
    return True

rank 数组记录树的“高度”近似值，合并时让矮树挂到高树上，避免树退化为链。

核心功能#

连通性判断：find(x) == find(y) 表示 x 和 y 在同一集合中。
动态添加关系：通过 union 合并两个节点所在的集合。
统计集合个数：遍历所有节点，find(i) == i 的个数即为集合数。

天梯L2-013-并查集模拟#

问题描述

1
def find(p,x):
2
    if p[x] != x:
3
        p[x] = find(p,p[x])
4
    return p[x]
5
def union(p,rank,x,y):
6
    rx,ry = find(p,x),find(p,y)
7
    if rx == ry:
8
        return
9
    if rank[rx] < rank[ry]:
10
        p[rx] = p[ry]
11
    elif rank[rx] > rank[ry]:
12
        p[ry] = p[rx]
13
    else:
14
        p[ry] = p[rx]
15
        rank[rx] += 1
16
def count_components(n, edges, lost):
17
    p = list(range(n))
18
    rank = [0]*n
19
    for u, v in edges:
20
        if not lost[u] and not lost[v]:
21
            union(p,rank,u,v)
22
    res = 0
23
    for i in range(n):
24
        if not lost[i] and p[i] == i:
25
            res += 1
26
    return res
27

28
def main():
29
    n, m = map(int, input().split())
30
    edges = []
31
    for _ in range(m):
32
        u, v = map(int, input().split())
33
        edges.append((u, v))
34
    k = int(input())
35
    lost = [False] * n
36
    prev_cnt = count_components(n, edges, lost)
37

38
    attacks = list(map(int, input().split()))
39
    for city in attacks:
40
        lost[city] = True
41
        cur_cnt = count_components(n, edges, lost)
42
        if cur_cnt > prev_cnt:
43
            print(f"Red Alert: City {city} is lost!")
44
        else:
45
            print(f"City {city} is lost.")
46
        prev_cnt = cur_cnt
47
    if all(lost):
48
        print("Game Over.")
49
if __name__ == "__main__":
50
    main()

天梯L2-024-并查集模拟#

问题描述

1
def find(p,x):
2
    if p[x] != x:
3
        p[x] = find(p,p[x])
4
    return p[x]
5
def union(p,rank,x,y):
6
    rx,ry = find(p,x),find(p,y)
7
    if rx == ry:
8
        return
9
    if rank[rx] < rank[ry]:
10
        p[rx] = p[ry]
11
    elif rank[rx] > rank[ry]:
12
        p[ry] = p[rx]
13
    else:
14
        p[ry] = p[rx]
15
        rank[rx] += 1
16
def main():
17
    n = int(input())
18
    MX = 10005
19
    p = list(range(MX))
20
    rank = [0]*MX
21
    people = set()
22
    for _ in range(n):
23
        d = list(map(int,input().split()))
24
        k = d[0]
25
        ids = d[1:]
26
        for id in ids:
27
            people.add(id)
28
        fir = ids[0]
29
        for pid in ids[1:]:
30

31
            union(p,rank,fir,pid)
32
    tot = len(people)
33
    root = set()
34
    for pid in people:
35
        root.add(find(p,pid))
36
    t = len(root)
37
    print(tot,t)
38
    q = int(input())
39
    for _ in range(q):
40
        a,b = map(int,input().split())
41
        if find(p,a) == find(p,b):
42
            print("Y")
43
        else:
44
            print("N")
45
if __name__ == "__main__":
46
    main()

力扣2316-统计每个连通块的大小#

问题描述

给定一个无向图，有 n 个节点，编号从 0 到 n-1。再给定一个边列表 edges，每条边连接两个节点。要求计算所有无法互相到达的节点对（即不存在路径连接的两个节点）的数目。注意，点对 (u, v) 和 (v, u) 视为同一个点对，只计一次。

1
class Solution:
2
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
3
        def find(p,x):
4
            if p[x] != x:
5
                p[x] = find(p,p[x])
6
            return p[x]
7
        def union(p,rank,x,y):
8
            rx,ry = find(p,x),find(p,y)
9
            if rx == ry:
10
                return
11
            if rank[rx] < rank[ry]:
12
                p[rx] = p[ry]
13
            elif rank[rx] > rank[ry]:
14
                p[ry] = p[rx]
15
            else:
16
                p[ry] = p[rx]
17
                rank[rx] += 1
18
        p = list(range(n))
19
        rank = [1]*n
20
        for x,y in edges:
21
            union(p,rank,x,y)
22
        # 统计每个连通块的大小
23
        root_cnt = Counter()
24
        for i in range(n):
25
            root = find(p,i)
26
            root_cnt[root] += 1
27
        tot = comb(n,2)
28
        r = 0
29
        for size in root_cnt.values():
30
            r += comb(size,2)
31
        return tot - r

洛谷P1197-连通块 + 离线逆序处理+邻接表（摧毁后连通块的个数）#

问题重述

有一个由 $n$ 个星球组成的星系，初始时某些星球之间通过双向的“以太隧道”相连（这些隧道构成一个无向图）。现在帝国会按顺序摧毁 $k$ 个星球（每次摧毁一个星球，该星球及其相连的所有隧道都会消失）。你需要计算每次摧毁后，剩下的星球之间形成的连通块的数量。输出初始状态（摧毁前）的连通块数，以及每摧毁一个星球后当前的连通块数。

1
import sys
2
sys.setrecursionlimit(200000)
3

4
def find(p, x):
5
    if p[x] != x:
6
        p[x] = find(p, p[x])
7
    return p[x]
8

9
def union(p, rank, x, y):
10
    rx, ry = find(p, x), find(p, y)
11
    if rx == ry:
12
        return
13
    if rank[rx] < rank[ry]:
14
        p[rx] = ry
15
    elif rank[rx] > rank[ry]:
16
        p[ry] = rx
17
    else:
18
        p[ry] = rx
19
        rank[rx] += 1
20

21
def solve():
22
    input = sys.stdin.readline
23
    n, m = map(int, input().split())
24
    edges = [[] for _ in range(n)]
25
    for _ in range(m):
26
        u, v = map(int, input().split())
27
        edges[u].append(v)
28
        edges[v].append(u)
29

30
    k = int(input())
31
    order = [int(input()) for _ in range(k)]
32
    destroyed = [False] * n
33
    for x in order:
34
        destroyed[x] = True
35

36
    parent = list(range(n))
37
    rank = [0] * n
38
    cnt = n - k  # 初始时，未被摧毁的星球都是孤立的
39

40
    # 先合并未被摧毁的星球之间的边
41
    for u in range(n):
42
        if not destroyed[u]:
43
            for v in edges[u]:
44
                if not destroyed[v] and u < v:  # 避免重复
45
                    if find(parent, u) != find(parent, v):
46
                        union(parent, rank, u, v)
47
                        cnt -= 1
48

49
    ans = [cnt]  # 最后一个状态（摧毁所有后）的连通块数
50

51
    # 逆序添加星球
52
    for x in reversed(order):
53
        destroyed[x] = False
54
        cnt += 1  # 新加一个孤立点
55
        for v in edges[x]:
56
            if not destroyed[v]:
57
                if find(parent, x) != find(parent, v):
58
                    union(parent, rank, x, v)
59
                    cnt -= 1
60
        ans.append(cnt)
61

62
    # 输出逆序结果（正序输出）
63
    for res in reversed(ans):
64
        print(res)
65

66
if __name__ == "__main__":
67
    solve()

力扣2316#

问题描述

1
class Solution:
2
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
3
        '''
4
        def find(p,x):
5
            if p[x] != x:
6
                p[x] = find(p,p[x])
7
            return p[x]
8
        def union(p,rank,x,y):
9
            rx,ry = find(p,x),find(p,y)
10
            if rx == ry:
11
                return
12
            if rank[rx] < rank[ry]:
13
                p[rx] = p[ry]
14
            elif rank[rx] > rank[ry]:
15
                p[ry] = p[rx]
16
            else:
17
                p[ry] = p[rx]
18
                rank[rx] += 1
19
        p = list(range(n))
20
        rank = [1]*n
21
        for x,y in edges:
22
            union(p,rank,x,y)
23
        # 统计每个连通块的大小
24
        root_cnt = Counter()
25
        for i in range(n):
26
            root = find(p,i)
27
            root_cnt[root] += 1
28
        tot = comb(n,2)
29
        r = 0
30
        for size in root_cnt.values():
31
            r += comb(size,2)
32
        return tot - r
33
        '''
34
        g = [[] for _ in range(n)]
35
        for x,y in edges:
36
            g[x].append(y)
37
            g[y].append(x)
38
        vis = [False]*n
39
        # DFS求连通块的数量
40
        def dfs(x):
41
            vis[x] = True
42
            size = 1
43
            for y in g[x]:
44
                if not vis[y]:
45
                    size += dfs(y)
46
            return size
47
        size = []
48
        for i in range(n):
49
            if not vis[i]:
50
                size.append(dfs(i))
51
        tot = comb(n,2)
52
        r = 0
53
        for s in size:
54
            r += comb(s,2)
55
        return tot - r

AWC53D-用并查集实现快速跳过已涂色的位置+倒序处理#

逆序遍历，用并查集实现快速跳过已染色的位置

问题描述

我们有 N 个位置（1 到 N），初始时全部未涂色。我们要从后往前处理区间 [l, r]，将区间内尚未涂色的位置涂上颜色。每个位置一旦被涂色，就不再处理（因为后面的操作会覆盖前面的，我们从后往前，所以第一次涂色就是最终颜色）。

我们需要一种方法，能快速找到区间 [l, r] 中下一个未涂色的位置。

1
import sys
2
def solve():
3
    input = sys.stdin.readline
4
    n, m = map(int, input().split())
5
    ops = [tuple(map(int, input().split())) for _ in range(m)]
6
    p = list(range(n + 3))
7
    def find(x):
8
        while p[x] != x:
9
            p[x] = p[p[x]]
10
            x = p[x]
11
        return x
12
    ans = [0] * (n + 1)
13
    for l, r, c in reversed(ops):
14
        pos = find(l) # 找到第一个未涂色的位置
15
        while pos <= r:
16
            ans[pos] = c
17
            p[pos] = find(pos + 1) # 将当前位置指向下一个位置
18
            pos = find(pos) # 继续找下一个未涂色位置
19
    print(' '.join(map(str, ans[1:])))
20
if __name__ == "__main__":
21
    solve()

力扣1722-使用并查集形成连通分量#

问题描述和题解思路

给定两个长度均为 $n$ 的整数数组 source 和 target，以及一个允许交换的索引对列表 allowedSwaps。你可以无限次交换 allowedSwaps 中任意一对索引对应的元素（交换操作可以传递，即如果 (a,b) 和 (b,c) 允许交换，那么 a 和 c 之间也可以间接交换）。通过任意次交换后，你可以重新排列 source 中那些属于同一连通分量的元素。目标是使最终 source 与 target 的 汉明距离 最小。汉明距离定义为不同位置上元素值的个数。求这个最小可能的汉明距离。

注意：交换只能在 allowedSwaps 给出的索引对之间进行（可传递），且每个连通分量内的元素可以任意排列（因为交换图是传递的）。因此，我们可以将数组索引视为图节点，allowedSwaps 为边，形成若干连通分量。在每个分量内，source 中的元素可以重新排列成任意顺序。为了最小化汉明距离，我们希望在每个位置上，尽量让 source 的元素与 target 对应位置的元素相等。因此，对于每个连通分量，我们统计该分量内 source 中各元素的频次和 target 中各元素的频次，然后可以匹配的数量就是两个频次对应元素的最小值之和，该分量内无法匹配的元素个数即为该分量的贡献。总汉明距离即为所有分量贡献之和。

具体解法：使用并查集合并所有可以交换的索引对，然后按根分组，对每个组分别统计 source 和 target 的元素频次，用 Counter 计算可匹配的对数（或者直接累加无法匹配的个数），最后求和得到最小汉明距离。

1
class Solution:
2
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
3
        def find(p,x):
4
            if p[x] != x:
5
                p[x] = find(p,p[x])
6
            return p[x]
7
        def union(p,rank,x,y):
8
            rx,ry = find(p,x),find(p,y)
9
            if rx == ry:
10
                return
11
            if rank[rx] < rank[ry]:
12
                p[rx] = p[ry]
13
            elif rank[rx] > rank[ry]:
14
                p[ry] = p[rx]
15
            else:
16
                p[ry] = p[rx]
17
                rank[rx] += 1
18
        n = len(source)
19
        p = list(range(n))
20
        rank = [0]*n
21
        for a,b in allowedSwaps:
22
            union(p,rank,a,b)
23
        g = defaultdict(list)
24
        for i in range(n):
25
            root = find(p,i)
26
            g[root].append(i)
27
        # print(g.values())
28
        ans = 0
29
        for idx in g.values():
30
            cnt = Counter()
31
            for i in idx:
32
                cnt[source[i]] += 1
33
            for i in idx:
34
                if cnt[target[i]] > 0:
35
                    cnt[target[i]] -= 1
36
                else:
37
                    ans += 1
38
        return ans

牛客140周赛E-使用并查集形成连通分量#

问题描述

1
def find(p, x):
2
    if p[x] != x:
3
        p[x] = find(p, p[x])
4
    return p[x]
5
def union(p, rank, x, y):
6
    rx, ry = find(p, x), find(p, y)
7
    if rx == ry:
8
        return False
9
    if rank[rx] < rank[ry]:
10
        p[rx] = p[ry]
11
    elif rank[rx] > rank[ry]:
12
        p[ry] = p[rx]
13
    else:
14
        p[ry] = p[rx]
15
        rank[rx] += 1
16
    return True
17
for _ in range(int(input())):
18
    n, x, y = map(int, input().split())
19
    p = list(map(int, input().split()))
20
    pa = list(range(n))
21
    rank = [0] * n
22
    for i in range(n):
23
        if i + x < n:
24
            union(pa, rank, i, i + x)
25
        if i + y < n:
26
            union(pa, rank, i, i + y)
27
    comp = {}
28
    for i in range(n):
29
        root = find(pa, i)
30
        if root not in comp:
31
            comp[root] = []
32
        comp[root].append(i)
33
    ok = True
34
    for idx in comp.values():
35
        val = [p[i] - 1 for i in idx]
36
        val.sort()
37
        if val != idx:
38
            ok = False
39
            break
40
    print("Yes" if ok else "No")

音乐

音乐

并查集#

原理和板子#

核心功能#

天梯L2-013-并查集模拟#

天梯L2-024-并查集模拟#

力扣2316-统计每个连通块的大小#

洛谷P1197-连通块 + 离线逆序处理+邻接表（摧毁后连通块的个数）#

力扣2316#

AWC53D-用并查集实现快速跳过已涂色的位置+倒序处理#

力扣1722-使用并查集形成连通分量#

牛客140周赛E-使用并查集形成连通分量#

文章分享

评论区

音乐

目录