130. 被围绕的区域

https://leetcode-cn.com/problems/surrounded-regions/

解法一：dfs

两次遍历。第一次先遍历边界，dfs将所有与边界O相连的O置为‘-’。之后再遍历所有，将所有O变为X，所有’-‘变为O

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if n == 0:
            return
        m = len(board[0])
        #对四条边界上的元素dfs遍历
        for i in range(n):            
            self.dfs(i, 0, n, m, board)
            self.dfs(i, m-1, n, m, board)
        for j in range(m):
            self.dfs(0, j, n, m, board)
            self.dfs(n-1, j, n, m, board)
        #遍历所有
        for i in range(n):
            for j in range(m):
            	#注意先后顺序不能颠倒
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == '-':
                    board[i][j] = 'O'
        
    def dfs(self, row, col, rows, cols, board):
        if row >= 0 and row < rows and col >= 0 and col < cols and board[row][col] == 'O':
            board[row][col] = '-'  #特殊标记
            #dfs遍历上下左右
            self.dfs(row, col-1, rows, cols, board)
            self.dfs(row, col+1, rows, cols, board)
            self.dfs(row-1, col, rows, cols, board)
            self.dfs(row+1, col, rows, cols, board)   

解法二：并查集

参考https://leetcode-cn.com/problems/surrounded-regions/solution/bfsdi-gui-dfsfei-di-gui-dfsbing-cha-ji-by-ac_pipe/

被x包围的o一定不与外界（设为“虚拟节点”）连通，例如边界的o与外界连通。用并查集找出不与外界连通的o，然后置为x即可。

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = totalNodes

    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	#注意：此处可优化（见优化二）
            self.parents[root2] = root1
        		# 连通分量数减一
        		self.count -= 1

    # 查找最终的根
    def find(self, node):
      			#注意：此处可优化（见优化一）
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or len(board) == 0:
            return
        rows = len(board)
        cols = len(board[0])
        uf = UnionFind(rows * cols + 1)  # 多出一个位置留给虚拟结点
        dummyNode = rows * cols  # 虚拟结点的一维坐标

        # 为简化算法，将二维坐标转换为一维坐标
        def node(i, j):
            return i * cols + j

        # 遍历所有点
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'O':
                    # 若是边界，则与虚拟结点合并
                    if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
                        uf.union(node(i, j), dummyNode)
                    else:
                        # 对上下左右的'O'结点进行合并
                        if i > 0 and board[i - 1][j] == 'O':
                            uf.union(node(i, j), node(i - 1, j))
                        if i < rows - 1 and board[i + 1][j] == 'O':
                            uf.union(node(i, j), node(i + 1, j))
                        if j > 0 and board[i][j - 1] == 'O':
                            uf.union(node(i, j), node(i, j - 1))
                        if j < cols - 1 and board[i][j + 1] == 'O':
                            uf.union(node(i, j), node(i, j + 1))
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'O':
                    # 与虚拟结点连通的点则保持'O'
                    if uf.isConnected(node(i, j), dummyNode):
                        board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'

优化

一、路径压缩

并查集的find函数可以改进

def find(self, node):
    while self.parents[node] != node:
        self.parents[node] = self.parents[self.parents[node]]
        node = self.parents[node]
        # 优化前
        # node = self.parents[node]
    return node

如下图

调用 find 函数每次向树根遍历的同时，顺手将树高缩短了，最终所有树高都不会超过 3（union 的时候树高可能达到 3）。

二、平衡性优化

我们一开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下面，那么这里就可能出现「头重脚轻」的不平衡状况，比如下面这种局面

长此以往，树可能生长得很不平衡。我们希望小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。解决方法是额外使用一个 size 数组，记录每棵树包含的节点数，称为“重量”（size）

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = totalNodes
        # 树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	# 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count