数据结构-并查集刷题

并查集及相关应用

基础知识部分

并查集可以解决连通性问题。 考虑平均查找次数，将节点数更少的树合并到节点数更多的树上，平均查找次数更少。
Quick-Find算法 思路：将同一组的节点染成相同的颜色
Quick-Union算法 思路：将连通关系转换为树形结构，通过递归的方式快速判定。
Weighted-Quick-Union算法 思路：通过考虑平均查找次数的方式，对合并过程进行优化。
带路径压缩的Weighted-Quick-Union算法
带路径压缩的并查集模板
思路：每次查询连通性关系时，对节点到根节点的路径上所有点进行优化，避免连通性关系从树型结构退 化成链表型结构。

并查集基础题目

547. 省份数量

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n + 1))
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        UF = UnionFind(len(isConnected))
        for i in range(len(isConnected)):
            for  j in range(len(isConnected)):
                if isConnected[i][j] == 1:
                    UF.merge(i, j) 
        ans = 0
        for i in range(len(isConnected)):
            if UF.find(i) == i: ans += 1
        return ans
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

200. 岛屿数量

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]

    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n = len(grid)
        m = len(grid[0])
        UF = UnionFind(n * m)
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    if i > 0 and grid[i - 1][j] == '1':
                        UF.merge(i * m + j,  (i -1) * m + j)
                    if j > 0 and grid[i][j - 1] == '1':
                        UF.merge(i * m + j, i * m  + j - 1)
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1' and UF.find(i * m + j) == i * m + j:
                    ans += 1
        return ans 
                # [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)] 
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

990. 等式方程的可满足性

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
    def isconnection(self, x, y):
        return self.find(x) == self.find(y)
class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        UF = UnionFind(26)
        for equation in equations:
            if equation[1] == '=':
                UF.merge(ord(equation[0]) - ord('a'), ord(equation[3]) - ord('a'))
        
        for equation in equations:
            if equation[1] == '!' and UF.isconnection(ord(equation[0]) - ord('a'), ord(equation[3]) - ord('a')):
                return False 
        return True
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

并查集进阶题目

684. 冗余连接

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n + 1))
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
    def isconnection(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        UF =UnionFind(len(edges))
        for edge in edges:
            if UF.isconnection(edge[0], edge[1]):
                return edge
            UF.merge(edge[0], edge[1])
        return []

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

1319. 连通网络的操作次数

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
    def isconnection(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if n - 1 > len(connections):
            return  -1
        UF = UnionFind(n)
        for connection in connections:
            UF.merge(connection[0], connection[1])
        ans = 0
        for i in range(n):
            if UF.find(i) == i: ans += 1
        return ans - 1
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

128. 最长连续序列

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
        self.count = [1 for _ in range(n)]
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.count[root_x] += self.count[root_y]
            self.father[root_y] = root_x
    def isconnection(self, x, y):
        return self.find(x) == self.find(y)
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        UF = UnionFind(len(nums))
        nums_map = dict()
        for i in range(len(nums)):
            if nums[i] in nums_map: continue
            nums_map[nums[i]] = i
            if nums[i] - 1 in nums_map:
                UF.merge(i, nums_map[nums[i] - 1])
            if nums[i] + 1 in nums_map:
                UF.merge(i, nums_map[nums[i] + 1])
        ans = 0
        for i in range(len(nums)):
            if UF.find(i) == i:
                ans = max(ans, UF.count[i])
        return ans 
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

947. 移除最多的同行或同列石头

1202. 交换字符串中的元素

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
    
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        UF = UnionFind(n)
        for pair in pairs:
            UF.merge(pair[0], pair[1])
        str_list = collections.defaultdict(list)

        for i in range(n):
            str_list[UF.find(i)].append(i)
        s1 = list(s)

        for idx_list in str_list.values():
            tem = [s[i] for i in idx_list]
            tem.sort()
            for i,  idx in enumerate(idx_list):
                s1[idx] = tem[i]
        return ''.join(s1)

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

721. 账户合并

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        email_account = dict()
        email_name = dict()
        idx = 0
        for account in accounts:
            for email in account[1:]:
                if email not in email_account:
                    email_account[email] = idx
                    idx += 1
                    email_name[email] = account[0]
        UF = UnionFind(len(email_account))
        for account in accounts:
            root_email = account[1]
            for email in account[2:]:
                UF.merge(email_account[root_email], email_account[email])
        msg = [[] for i in range(len(email_account))] # 放每个集合邮箱
        for email, idx in email_account.items():
            idx = UF.find(idx)
            msg[idx].append(email)
        ans = []
        for data in msg:
            if data:
                tem = sorted(data)
                name = email_name[data[0]]
                ans.append([name] + tem)
        return ans       

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

并查集附加题

765. 情侣牵手

class UnionFind:
    def __init__(self, n): # 初始化元素 
        self.father = dict()
        for i in range(0, n * 2, 2):
            self.father[i] = i
    
    def find(self, val): # 查找父节点 
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):  #合并元素
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
    
    def isconnection(self, x, y):
        return self.find(x) == self.find(y)
    def count(self):
        count = dict()
        for val in self.father.values():
            val = self.find(val)
            if val not in count:
                count[val] = 0
            count[val] += 1
        return [val for val in count.values()]

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row) // 2
        UF = UnionFind(n)
        for i in range(0, 2 * n, 2):
            if row[i] % 2 == 0: # 第一个人是情侣代表
                if row[i] + 1 != row[i + 1]: # 判断第二个人是不是第一个的伴侣
                    if row[i + 1] % 2 == 0:
                        UF.merge(row[i], row[i+1])
                    else: # 第二个人不是情侣代表 
                        UF.merge(row[i], row[i+1] - 1)
            else: # 第一个人不是情侣代表 
                if row[i] - 1 != row[i + 1]: # 判断第二个人是不是第一个的伴侣
                    if row[i+1] % 2 == 0: # 第二个人也是情侣代表 
                        UF.merge(row[i] - 1, row[i+1])
                    else: # 第二人不是情侣代表 
                        UF.merge(row[i] - 1, row[i+1] - 1)
        tem = UF.count()
        return sum(tem) - len(tem)

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

685. 冗余连接 II

class UnionFind:
    def __init__(self):
        self.father = list()

    def make_init(self, n):
        self.father = list(range(n + 1))
        self.condition2  = 0 

    def find(self, val):
        if self.father[val] == val:
            return val
        self.father[val] = self.find(self.father[val])
        return self.father[val]
    
    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x
        else:
            self.condition2 = 1
    def isconnection(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        UF = UnionFind()
        for i in range(n): # 排序一个边 
            x, y = edges[n - 1 - i]
            vis = [0 for _ in range(n + 1)]
            UF.make_init(n)
            condition1 = 0
            for j in range(n):
                if edges[j][0] == x and edges[j][1] == y:
                    continue
                UF.merge(edges[j][0], edges[j][1])
                vis[edges[j][1]] += 1 # 计数入度 + 1
                if vis[edges[j][1]] > 1:
                    # 表示触发条件
                    condition1 = 1
                    break
            if condition1 == 0 and UF.condition2 == 0:
                return [x, y]
        return [-1. -1
        ]
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