• 概述

    并查集是一种能够高效判断两个数是否属于同一个集合的数据结构，并且可以动态合并。

    • 模版

      1. n = 10
      2. f = list(range(n))
      3. def find(x):
      4.   if f[x] != x:
      5.       f[x] = find(f[x])
      6.   return f[x]
      7. def union(x, y):
      8.      f[find(x)] = find(y)
      9. def getGroup():  # 返回分组 key为父节点 value为同组的成员
      10.   group = collections.defaultdict(list)
      11.   for i, j in enumerate(map(find, f)):
      12.       group[j].append(i)
      13.   return group
      14. def connected(x, y):
      15.   return find(x) == find(y)
      16. def getComponent():  # 获取连通分量数
      17.   return sum(find(i) == i for i in range(n))

    • 执行交换操作后的最小汉明距离

    给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

    相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

    在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations
    参考解答：

    1. class Solution:
    2.     def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
    3.         n = len(source)
    4.         f = list(range(n))
    5.         def find(x):
    6.             if f[x] != x:
    7.                 f[x] = find(f[x])
    8.             return f[x]
    9.         def union(x, y):
    10.             f[find(x)] = find(y)
    11.         def getGroup():
    12.             group = collections.defaultdict(list)
    13.             for i, j in enumerate(map(find, f)):
    14.                 group[j].append(i)
    15.             return group
    16.         for x, y in allowedSwaps:
    17.             union(x, y)
    18.         group = getGroup()
    19.         ans = 0
    20.         for idx in group.values():
    21.             t = Counter([target[i] for i in idx])
    22.             for i in idx:
    23.                 if t[source[i]] > 0:
    24.                     t[source[i]] -= 1
    25.                 else:
    26.                     ans += 1
    27.         return ans
    • 并查集优化：含size的并查集

    维护一个size数组，用于记录节点个数。

    1. size = [1] * n
    2. def union(p, q):
    3.     pRoot = find(p)
    4.     qRoot = find(q)
    5.     if pRoot != qRoot:
    6.         if size[pRoot] < size[qRoot]:
    7.             f[pRoot] = qRoot
    8.             size[qRoot] += size[pRoot]
    9.         else:
    10.             f[qRoot] = pRoot
    11.             size[pRoot] += size[qRoot]
    12. def getSize(p):
    13.     return size[find(p)]
    • 打砖块

    有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

    一块砖直接连接到网格的顶部，或者
    至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
    给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。

    返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

    注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/bricks-falling-when-hit
    分析：
    因为之前打下的砖块会对之后的砖块产生影响，所以采用逆向思维，将hits数组逆序，想象成依次添加砖块，看添加前后增加了多少砖块和顶部直接相连。
    参考解答：

    class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        row, col = len(grid), len(grid[0])
        copy = [[grid[i][j] for j in range(col)] for i in range(row)]  # 不改变输入数据。
        for r, c in hits:
            copy[r][c] = 0  # 先将所有的砖块敲掉，然后逆序添加
        roof = row * col # 表示顶部的id
        f = list(range(roof + 1))
        size = [1] * (roof + 1)
        def find(p):
            if f[p] != p:
                f[p] = find(f[p])
            return f[p]
        def union(p, q):
            pRoot = find(p)
            qRoot = find(q)
            if pRoot != qRoot:
                if size[pRoot] < size[qRoot]:
                    f[pRoot] = qRoot
                    size[qRoot] += size[pRoot]
                else:
                    f[qRoot] = pRoot
                    size[pRoot] += size[qRoot]
        def getSize(p):
            return size[find(p)]
        for i in range(row):
            for j in range(col):
                if copy[i][j] == 0:
                    continue
                if i == 0:  # 和顶部相连
                    union(j, roof)
                if i > 0 and copy[i-1][j] == 1:  # 建图
                    union((i-1)*col+j, i*col+j)
                if j > 0 and copy[i][j-1] == 1:
                    union(i*col+j-1, i*col+j)
        d = [[-1,0], [1,0], [0,1], [0,-1]]
        ret = [0] * len(hits)
        for i in range(len(hits)-1, -1, -1):
            x, y = hits[i]
            if grid[x][y] == 0:  # 需要敲掉的位置无砖 
                continue
            origin = getSize(roof) # 添加之前稳定的砖块数
            if x == 0:
                union(y, roof)
            for dx, dy in d:
                nx = x + dx
                ny = y + dy
                if 0 <= nx and nx < row and 0 <= ny and ny < col and copy[nx][ny] == 1:
                    union(nx*col+ny, x*col+y)
            current = getSize(roof) # 添加之后稳定的砖块数
            ret[i] = max(0, current-origin-1)  # 可能添加后并不会增加稳定砖块的个数
            copy[x][y] = 1 # 添加砖块
        return ret