作用：检查图上面是否存在环

image.png
先将连通的节点加入集合，如果再选中的边的两个顶点已经在集合里了，说明出现环

合并算法：
1.一维数组image.png 全是 -1 初始化表示独立
parent[1] = 0 说明1的父节点是0
parent[2]= 0 说明2的父节点也是0
012三个节点就可以连接起来

2.如何连接两棵树（并）
image.png
为了不形成断层和路径过长
分别找到父节点，然后连接（查）image.png

结论：构造出parent数组之后，如果两个节点根节点一样，则说明有环
image.png

image.png
寻找x, y的根节点 x_root, y_root然后合并

分为两个函数find_root(), union() 找根节点和合并（）查和并

  1. n = len(verticices)
  2. parent = [-1] * n
  4. ## 找到根节点(-1)为止
  5. def find_root(x, parent):
  6.     x_root = x
  7.     while parent[x_root] != -1:
  8.         x_root = parent[x_root]
  9.     return x_root
  11. ## return: True/False
  12. def union(x, y, parent):
  13.     x_root = find_root(x)
  14.     y_root = find_root(y)
  16.     if x_root == y_root:
  17.         return False
  18.     parent[x_root] = y_root
  19.     return True

union算法问题：如果图链特别长，查找parent数组复杂度将会变成o(logn)？复杂度
引进新变量 Rank
image.png

  1. n = len(verticices)
  2. parent = [-1] * n
  3. rank = [0] * n
  4. ## 找到根节点(-1)为止
  5. def find_root(x, parent):
  6.     x_root = x
  7.     while parent[x_root] != -1:
  8.         x_root = parent[x_root]
  9.     return x_root
  11. ## return: True/False
  12. def union(x, y, parent, rank):
  13.     x_root = find_root(x)
  14.     y_root = find_root(y)
  16.     if x_root == y_root:
  17.         return False
  18.     ## 路径压缩算法
  19.     if rank[x_root] > rank[y_root]:
  20.         parent[y_root] = x_root
  21.     elif rank[y_root] > rank[x_root]:
  22.         parent[x_root] = y_root
  23.     else:
  24.         parent[y_root] = x_root
  25.         rank[x_root] += 1
  26.     return True

总结: parent[], rank []
find_root()
union() + 路径压缩

模板

  1. class UnionFind:
  2.     def __init__(self):
  3.         """
  4.         记录每个节点的父节点
  5.         """
  6.         self.father = {}
  8.     def find(self,x):
  9.         """
  10.         查找根节点
  11.         路径压缩
  12.         """
  13.         root = x
  15.         while self.father[root] != None:
  16.             root = self.father[root]
  18.         # 路径压缩
  19.         while x != root:
  20.             original_father = self.father[x]
  21.             self.father[x] = root
  22.             x = original_father
  24.         return root
  26.     def merge(self,x,y,val):
  27.         """
  28.         合并两个节点
  29.         """
  30.         root_x,root_y = self.find(x),self.find(y)
  32.         if root_x != root_y:
  33.             self.father[root_x] = root_y
  35.     def is_connected(self,x,y):
  36.         """
  37.         判断两节点是否相连
  38.         """
  39.         return self.find(x) == self.find(y)
  41.     def add(self,x):
  42.         """
  43.         添加新节点
  44.         """
  45.         if x not in self.father:
  46.             self.father[x] = None
  48. 作者：MiloMusiala
  49. 链接：https://leetcode-cn.com/problems/evaluate-division/solution/pythonbing-cha-ji-fu-mo-ban-by-milomusia-kfsu/
  50. 来源：力扣（LeetCode）
  51. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。