基础知识：
https://leetcode-cn.com/problems/satisfiability-of-equality-equations/solution/shou-hui-tu-jie-shou-xie-unionfind-bing-cha-ji-bu-/
130、被围绕的区域
具体实现：
靠边的O都不可能被替换，与这些O连接的O也不会被替换，抽象出一个dummy节点，这些O是dummy节点的子节点
二维坐标映射到一维左边的常用技巧：
m是行数，n是列数，二维坐标（i，j）可以转换成i*n+y
代码：
class Solution: class UnionFind: def __init__(self,totalNodes): self.parents = list(range(totalNodes)) def union(self, index1, index2): root1 = self.find(index1) root2 = self.find(index2) if root2!=root1: self.parents[root2] = root1 def find(self,node): while self.parents[node] != node: self.parents[node] = self.parents[self.parents[node]] node = self.parents[node] return node #当前节点的父节点 指向父节点的父节点. #保证一个连通区域最终的parents只有一个. def isConnected(self,node1,node2): return self.find(node1) == self.find(node2) def solve(self, board: List[List[str]]) -> None: if len(board)== 0 : return m = len(board) n = len(board[0]) uf = Solution.UnionFind(m*n+1) dummy = m*n for i in range(m): for j in range(n): if board[i][j] == 'O': if i == 0 or i == m-1 or j == 0 or j == n-1: uf.union(i*n+j,dummy) else: if i>0 and board[i-1][j] == 'O': uf.union(i*n+j,(i-1)*n+j) if i < m - 1 and board[i + 1][j] == 'O': uf.union(i*n+j, (i+1)*n+j) if j > 0 and board[i][j - 1] == 'O': uf.union(i*n+j, i*n+j-1) if j < n - 1 and board[i][j + 1] == 'O': uf.union(i*n+j, i*n+j+1) for i in range(m): for j in range(n): if uf.isConnected(i*n+ j, dummy): #和dummyNode 在一个连通区域的,那么就是O； board[i][j] = 'O' else: board[i][j] = 'X'
990、判定合法等式
具体实现：
如果是等号就连接两个节点，
如果是不等号就判断这两个节点是否是同一个根节点
是的话就判断为False
代码：
class Solution: class UnionFind: def __init__(self): self.parent = list(range(26)) def find(self, index): if index == self.parent[index]: return index self.parent[index] = self.find(self.parent[index]) return self.parent[index] def union(self, index1, index2): self.parent[self.find(index1)] = self.find(index2) def equationsPossible(self, equations: List[str]) -> bool: uf = Solution.UnionFind() for st in equations: if st[1] == "=":#如果是等于号就连接两个节点 index1 = ord(st[0]) - ord("a") index2 = ord(st[3]) - ord("a") uf.union(index1, index2) for st in equations: if st[1] == "!":#如果是不等于号 index1 = ord(st[0]) - ord("a") index2 = ord(st[3]) - ord("a") if uf.find(index1) == uf.find(index2):#判断这两个节点是否是一个根节点 return False #是的话就放回False return True