放两个模板
模版一：
初始化状态下，每个节点都不在子集合里，根节点的parent是None

  1. class UnionFind:
  2.     def __init__(self):
  3.         """
  4.         记录每个节点的父节点
  5.         """
  6.         self.father = {}
  7.     def find(self,x):
  8.         """
  9.         查找根节点
  10.         路径压缩
  11.         """
  12.         root = x
  13.         while self.father[root] != None:
  14.             root = self.father[root]
  15.         # 路径压缩
  16.         while x != root:
  17.             original_father = self.father[x]
  18.             self.father[x] = root
  19.             x = original_father
  20.         return root
  21.     def merge(self,x,y,val):
  22.         """
  23.         合并两个节点
  24.         """
  25.         root_x,root_y = self.find(x),self.find(y)
  27.         if root_x != root_y:
  28.             self.father[root_x] = root_y
  29.     def is_connected(self,x,y):
  30.         """
  31.         判断两节点是否相连
  32.         """
  33.         return self.find(x) == self.find(y)
  34.     def add(self,x):
  35.         """
  36.         添加新节点
  37.         """
  38.         if x not in self.father:
  39.             self.father[x] = None

模板二：
初始状态下所有节点的parent是他自己，所有没有了add函数，而且在find root函数里判断条件不是parent为None,而是parent为自身

1202. 交换字符串中的元素

  1. class UnionFind:
  2.     def __init__(self,n):
  3.         self.parent = [i for i in range(n)]
  4.     def find(self, x):
  5.         root = x
  6.         while self.parent[root]!=root:
  7.             root = self.parent[root]
  8.         while x!=root:
  9.             self.parent[x],x, = root ,self.parent[x]
  10.         return root
  11.     def union(self,x,y):
  12.         root_x, root_y = self.find(x), self.find(y)
  13.         if root_x!=root_y:
  14.             self.parent[root_x]=root_y
  16. from collections import defaultdict
  17. class Solution:
  18.     def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
  19.         uf = UnionFind(len(s))
  20.         for i,j in pairs:
  21.             uf.union(i,j)
  22.         children = defaultdict(lambda: set())
  23.         for i,j in pairs:
  24.             root = children[uf.find(i)]
  25.             root.add(i)
  26.             root.add(j)
  27.         arr = list(s)
  28.         for v in children.values():
  29.             for i,j in zip(sorted(v),sorted([arr[i] for i in v])):
  30.                 arr[i]=j
  31.         return "".join(arr)

200. 岛屿数量

https://leetcode-cn.com/problems/number-of-islands/
岛屿的数量还是用DFS写起来好理解一些

1319. 连通网络的操作次数

https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/

  1. n台计算机至少需要n-1条线才能全部联通
  2. 用并查集计算有多少个cluster，那么至少需要cluster-1条多余的连接线才可以做到全连通

  3. 如何计算多余的线？ 其实并不需要计算，因为如果两个cluster之间没有足够的线把他们链接起来，那么就已经不满足第一个条件了

    1. class UnionFind:
    2.  def __init__(self, n):
    3.      self.family = [i for i in range(n)]
    4.      self.redundant = 0
    6.  def find(self,x):
    7.      root = x
    8.      while self.family[root]!=root:
    9.          root = self.family[root]
    11.      while root!=x:
    12.          self.family[x], x = root, self.family[x]
    13.      return root
    15.  def union(self,x,y):
    16.      root_x, root_y = self.find(x), self.find(y)
    17.      if root_x!=root_y:
    18.          self.family[root_x] = root_y
    20.  def is_connected(self,x,y):
    21.      return self.find(x) == self.find(y)
    22. class Solution:
    23.  def makeConnected(self, n: int, connections: List[List[int]]) -> int:
    24.      if len(connections) < n-1:
    25.          return -1
    26.      uf = UnionFind(n)
    27.      for a,b in connections:
    28.          if uf.is_connected(a,b):
    29.              uf.redundant+=1
    30.          uf.union(a, b)
    31.      clusters = 0
    32.      for i in range(n):
    33.          if uf.family[i]==i:
    34.              clusters+=1
    35.      if uf.redundant < clusters-1:
    36.          return -1
    37.      else:
    38.          return clusters-1