并查集


preface

并查集,通常用于处理动态 联通性 的问题

  • 基本操作
    • 查询 Find
    • 合并 Union
  • 基本思想
    • 代表元
    • 路径压缩
  • 解题模板:
f = {}
def find(x):
    f.setdefault(x, x)
    while x != f[x]:
        f[x] = f[f[x]]
        x = f[x]
    return x
def union(x, y):
    f[find(x)] = find(y)

基础题目

990. 等式方程的可满足性

思路:普通并查集

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        f = {}
        def find(x):
            f.setdefault(x,x)
            while x!=f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x,y):
            f[find(x)] = find(y)
        
        for e in equations:
            a,b,c,d = tuple(e)
            if b=="=":
                union(a,d)
        for e in equations:
            a,b,c,d = tuple(e)
            if b == "!":
                if find(a)==find(d):
                    return False
        return True

547. 省份数量

思路:普通并查集

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        ans = n
        f = {}
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x,y):
            f[find(x)] = f[y]
        
        for x in range(n):
            for y in range(n):
                if isConnected[x][y] and find(x)!=find(y):
                    union(x,y)
                    ans -= 1

        return ans

684. 冗余连接

思路:逐边连接,若发现边的两个点是同一个根,则会连成环

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        f = {}
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x, y):
            f[find(x)] = find(y)

        for x,y in edges:
            if find(x) == find(y):
                return [x, y]
            union(x, y)

1319. 连通网络的操作次数

思路:普通并查集

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        m = len(connections)  #线缆数
        if n > m+1: return -1

        f = {}
        res = n-1
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x, y):
            f[find(x)] = find(y)

        for x,y in connections:
            if find(x)!=find(y):
                union(x, y)
                res -= 1
        return res

765. 情侣牵手

题意化简抽象的过程,有些复杂。。。

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)//2    # 情侣对数
        f = {}             # uf模板
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x, y):
            f[find(x)] = find(y)

        cnt = n                     # 联通分量,每个点代表一对情侣
        for i in range(0,n*2,2):
            if find(row[i]//2) != find(row[i+1]//2):   #不是一对(一堆)
                union(row[i]//2, row[i+1]//2)
                cnt -= 1
        return n-cnt

这题暴力也行…

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int: # 暴力解,异或运算
        result = 0
        for i in range(0, len(row), 2):
            if row[i] == row[i + 1] ^ 1: # 运用异或运算判断是不是一对情侣
                continue
            for j in range(i + 2, len(row), 1): # 如果不是,再进行搜寻
                if row[j] ^ 1 == row[i]: # 搜到了,那么接下来进行座位交换
                    row[i + 1], row[j] = row[j], row[i + 1]
                    result += 1 # 交换次数+1
                    break
        return result # 得到总的交换次数

进阶题目

99. 除法求值

并查集的同时维护变量间的倍数关系

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        f = {}  #记录每个结点的root
        d = {}  #记录每个结点到root的权

        def find(x):  #找到x的根节点并整理
            f.setdefault(x, x)
            d.setdefault(x,1)
            if x != f[x]:
                t = f[x]
                f[x] = find(t)
                d[x] *= d[t]
                return f[x]
            return x 

        def union(x, y, value):
            a, b = find(x), find(y)
            if a != b:
                f[a] = b   # a 的根结点是b
                d[a] = d[y] / d[x] * value  # a在b树上的权

        def check(x, y):
            if x not in f or y not in f:
                return -1.0
            a, b = find(x), find(y)
            if a != b: return -1.0 #ab不在一棵树
            return d[x] / d[y]

        for (x,y),v in zip(equations,values):
            union(x, y, v)

        return [check(x,y) for x,y in queries]

#不太懂啊。。。

DFS 会简单些

959. 由斜杠划分区域

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        cnt = n*n*4
        f = {}
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union (x, y):
            nonlocal cnt
            if find(x) != find(y):
                f[find(x)] = find(y)
                cnt -= 1

        def get_pos(row,col,i):
            return (row*n+col)*4+i

        for i in range(n):
            for j in range(n):
                v=grid[i][j]
                if j>0:
                    union(get_pos(i,j-1,1),get_pos(i,j,3))
                if i>0:
                    union(get_pos(i-1,j,2),get_pos(i,j,0))
                if v=='/':
                    union(get_pos(i,j,0),get_pos(i,j,3))
                    union(get_pos(i,j,1),get_pos(i,j,2))
                elif v=='\\':
                    union(get_pos(i,j,0),get_pos(i,j,1))
                    union(get_pos(i,j,2),get_pos(i,j,3))
                else:  
                    union(get_pos(i,j,0),get_pos(i,j,1))
                    union(get_pos(i,j,2),get_pos(i,j,3))
                    union(get_pos(i,j,1),get_pos(i,j,2))
        return cnt

778. 水位上升的泳池中游泳

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        f = {}                  #并查集板子
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x, y):
            f[find(x)] = find(y)

        rows, cols = len(grid), len(grid[0])   #准备工作
        edges = []
        for i in range(rows):
            for j in range(cols):
                idx = i*cols + j
                if i:
                    edges.append([idx,idx-cols,max(grid[i][j],grid[i-1][j])])
                if j:
                    edges.append([idx, idx-1, max(grid[i][j],grid[i][j-1])])
        edges.sort(key = lambda x:x[2])

        res = 0
        for x,y,w in edges:            #从最小花费边处理
            if find(x) == find(y):
                continue
            union(x,y)
            res = w
            if find(0) == find(rows*cols-1):
                break
        return res

1202. 交换字符串中的元素

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        f = {}                     #并查集板子
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x, y):
            f[find(x)] = find(y)

        for x,y in pairs:
            union(x,y)
        
        d = defaultdict(list)    #建立顺序关系
        for i in range(len(s)):
            d[find(i)].append(i)

        #print(d)
        res = list(s)                #开始处理
        for arr in d.values():
            target = sorted(arr, key = lambda x:s[x])
            for i,j in zip(arr,target):
                res[i] = s[j]
        return "".join(res)

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

最多可以移除的石头的个数 = 所有石头的个数 - 连通分量的个数。

# x 坐标,编号为 x 点
# y 坐标,编号为 10001 + y 点
# 对每个坐标开始联通

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        f = {}                     #并查集板子
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x, y):
            f[find(x)] = find(y)

        for x,y in stones:
            union(x, 10001+y)

        return len(stones) - len({find(x) for x,y in stones})

803. 打砖块

#脾气暴躁,不打了不打了

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录