数据结构之并查集

并查集

class UnionFind:
    def __init__(self, n: int):
        self.rank = [1] * n
        self.root = list(range(n))

    def find(self, x: int) -> int:
        if self.root[x] != x: self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: int, y: int) -> bool:
        rootx, rooty = self.find(x), self.find(y)
        if rootx == rooty: return False
        if self.rank[rootx] < self.rank[rooty]:
            rootx, rooty = rooty, rootx
        self.rank[rootx] += self.rank[rooty]
        self.root[rooty] = rootx
        return True

或者利用字典：

f={}
def find(x):
	f.setdefault(x,x)
	if x!=f[x]:
		f[x]=find(f[x])
	return f[x]

def union(x,y):
	f[find(x)]=f[find(y)]

被围绕的区域

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        f={}
        def find(x):
            f.setdefault(x,x)
            if x!=f[x]:
                f[x]=find(f[x])
            return f[x]
        
        def union(x,y):
            f[find(x)]=f[find(y)]
        
        row,col=len(board),len(board[0])
        inf=row*col

        for i in range(row):
            for j in range(col):
                if board[i][j]=='O':
                    if i==0 or i==row-1 or j==0 or j==col-1:
                        union(i*col+j,inf)  # 收集所有边界O
                    else:
                        for x,y in [(0,1),(0,-1),(1,0),(-1,0)]:
                            if board[i+x][j+y]=='O':
                                union(i*col+j,(i+x)*col+(j+y))  # 连通非边界O
        
        for i in range(row):
            for j in range(col):
                if find(i*col+j)==find(inf):
                    board[i][j]='O'
                else:
                    board[i][j]='X'

省份数量

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        f={}
        def find(x):
            f.setdefault(x,x)
            if x!=f[x]:
                f[x]=find(f[x])
            return f[x]
        
        def union(x,y):
            f[find(x)]=f[find(y)]
        
        row,col=len(isConnected),len(isConnected[0])
        for i in range(row):
            for j in range(col):
                if isConnected[i][j]:
                    union(i,j)

        for k in f.keys():
            f[k]=find(f[k])
        
        return len(set(f.values()))

冗余连接

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

        def union(x,y):
            f[find(x)]=f[find(y)]
        
        for tmp in edges:
            if find(tmp[0])!=find(tmp[1]):
                union(tmp[0],tmp[1])
            else:
                return [tmp[0],tmp[1]]