Python-并查集详解与实现

ゞ 浴缸里的玫瑰 2023-01-05 12:56 110阅读 0赞

目录

简介

初始化（帮派林立）

查询与合并（帮派争斗）

路径压缩（大江湖帮派争斗）

按高度合并

按节点总数合并

结果

全部代码

相关题目

简介

数据结构：树的双亲表示法，即一个列表fa，fa[i] = j，i的父节点为j

采用经典的帮派打架【找不到谁是第一作者了，在此表示感谢】来讲解：帮派->树、老大->根节点。

初始化（帮派林立）

刚开始，江湖上有很多帮派，帮派就一个人，“张三派”、“李四派”等，谁也不服谁。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 初始化，绿色代表根节点

  1. def __init__(self, n, hi=False):
  2.         self.fa = [i for i in range(n)]

每个帮派只有一个人，即自己是自己的老大==>自己是自己的根节点。

查询与合并（帮派争斗）

江湖开始了不断的厮杀。。。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1 合并

2->1：1和2打了一架，2输了，1说：“你输了，我以后就是你老大了”

5->3：5和3打了一架，5输了，3说：“你输了，我以后就是你老大了”

6->4：自行补充

4->3：自行补充

3->1：2和5要打架，他俩寻思，我们都有老大了，咱俩不管谁赢了，老大不服气，还是要打架，干脆让他俩打吧，谁老大输了，直接老大带着整个帮派拜另一个帮派的老大为老大，于是，2找了老大1，5找了老大3，1和3打了一架，3输了，于是3带着5、4、6都投奔到了1的门下。

  1. def find(self, val):
  2.         """
  3.         normal find, get father of val
  4.         :param val: a node's value
  5.         :return: root of val
  6.         """
  7.         if self.fa[val] == val:
  8.             return val
  9.         else:
  10.             return self.find(self.fa[val])

找到老大==>找到根节点

参数

val：节点的值

  1. def union(self, val1, val2):
  2.         """
  3.         normal union, make val1's father equal val2's father
  4.         :param val1: a node's value
  5.         :param val2: another node's value
  6.         :return: None
  7.         """
  8.         self.fa[self.find(val1)] = self.fa[self.find(val2)]
  9.         return None

输的一派的老大拜赢得帮派的老大为老大==>【val1是输的】val1所在树的根节点的父节点为val2所在树的根节点

合并树/集合

参数

val1:需要被合并的

val2:合并其他树/集合的

路径压缩（大江湖帮派争斗）

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2

假如上面的江湖之中，6先和5打架，之后是5和4，每次都是后者赢，依次类推，形成上图（左）。又有另一江湖，形成了上图（右），此时，6和另一帮派的…想要打架，…可能是10000甚至更多，等它找到他的老大时就太晚了。由于我们只关心谁是帮派的老大，所以可以在每次查询老大时，把沿途的每个节点的父节点都设为根节点

比喻结束！！！

按高度合并

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3

实际上，没有输赢，我们才是“幕后黑手”。前面的合并是我们随意选择的，并没有根据帮派（树）的特点来进行合并。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 4

为了让江湖厮杀更快一点，我们每次都让低的树合并到高的一方，即上图（右），而不是上图（左）。这样让合并后的树相对低一点。

  1. def union_compress(self, val1, val2):
  2.         """
  3.         union according to height of tree
  4.         :param val1:  a node's value
  5.         :param val2:  another node's value
  6.         :return: None
  7.         """
  8.         x, y = self.find(val1), self.find(val2)
  9.         if self.hi[x] <= self.hi[y]:
  10.             self.fa[x] = y
  11.         else:
  12.             self.fa[y] = x
  13.         if self.hi[x] == self.hi[y] and x != y:
  14.             self.hi[y] += 1
  15.         return None

根据高度合并，不像前面一定是第一个节点所在树合并到第二个上

参数

  • val1：节点的值

  • val2：另一节点的值

    def find_compress(self, val):

    1.     """
    2.     find with path compress
    3.     :param val:  a node's value
    4.     :return: father of val, val 's father equal val's root
    5.     """
    6.     if self.fa[val] == val:
    7.         return val
    8.     else:
    9.         self.fa[val] = self.find(self.fa[val])
    10.         return self.fa[val]

查找时路径压缩，找根节点时，设置自己的父节点为根节点

val：节点的值

按节点总数合并

仅提一下，不画图了。按秩合并的一种，秩的选取为树的节点总数，稍微改一下就好了。还有其他的路径压缩方法，不一一列举了。

结果

输入数据

7
2 1
5 3
6 4
4 3
5 2

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 5 无路径压缩

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 6

有路径压缩时，对应的最后一步合并如下。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 7

全部代码

  1. """
  2. --coding:utf-8--
  3. @File: DisjointSet.py.py
  4. @Author:frank yu
  5. @DateTime: 2021.01.17 19:50
  6. @Contact: frankyu112058@gmail.com
  7. @Description:
  8. """
  11. class DisjointSet:
  12.     def __init__(self, n, hi=False):
  13.         self.fa = [i for i in range(n)]
  14.         self.hi = []
  15.         if hi:
  16.             self.hi = [1 for _ in range(n)]
  18.     def union(self, val1, val2):
  19.         """
  20.         normal union, make val1's father equal val2's father
  21.         :param val1: value of node which need to change root
  22.         :param val2: another node's value
  23.         :return: None
  24.         """
  25.         self.fa[self.find(val1)] = self.find(val2)
  26.         return None
  28.     def find(self, val):
  29.         """
  30.         normal find, get father of val
  31.         :param val: a node's value
  32.         :return: root of val
  33.         """
  34.         if self.fa[val] == val:
  35.             return val
  36.         else:
  37.             return self.find(self.fa[val])
  39.     def union_compress(self, val1, val2):
  40.         """
  41.         union according to height of tree
  42.         :param val1:  a node's value
  43.         :param val2:  another node's value
  44.         :return: None
  45.         """
  46.         x, y = self.find(val1), self.find(val2)
  47.         if self.hi[x] <= self.hi[y]:
  48.             self.fa[x] = y
  49.         else:
  50.             self.fa[y] = x
  51.         if self.hi[x] == self.hi[y] and x != y:
  52.             self.hi[y] += 1
  53.         return None
  55.     def find_compress(self, val):
  56.         """
  57.         find with path compress
  58.         :param val:  a node's value
  59.         :return: father of val, val 's father equal val's root
  60.         """
  61.         if self.fa[val] == val:
  62.             return val
  63.         else:
  64.             self.fa[val] = self.find(self.fa[val])
  65.             return self.fa[val]
  67.     def show(self):
  68.         print(self.fa)
  71. def menu():
  72.     print('--------------------Menu--------------------')
  73.     print('1.Normal                2.Compress')
  74.     print('e.Exit')
  77. if __name__ == '__main__':
  78.     while True:
  79.         menu()
  80.         choice = input('please select an option：')
  81.         if choice == 'e':
  82.             break
  83.         n = input('please input number of nodes：')
  84.         if choice == '1':
  85.             d = DisjointSet(int(n))
  86.             print('please input a pair of nodes(the tree of the first one will join into the second one, # means stop)')
  87.             while True:
  88.                 seq = input()
  89.                 if seq == '#':
  90.                     break
  91.                 else:
  92.                     i, j = list(map(int, seq.split()))
  93.                     d.union(i, j)
  94.                     d.show()
  95.         else:
  96.             d = DisjointSet(int(n), True)
  97.             print('please input a pair of nodes(the tree of the first one will join into the second one, # means stop)')
  98.             while True:
  99.                 seq = input()
  100.                 if seq == '#':
  101.                     break
  102.                 else:
  103.                     i, j = list(map(int, seq.split()))
  104.                     d.union_compress(i, j)
  105.                     d.show()

相关题目

Leetcode 547 省份数量

Leetcode 200 岛屿数量

除法求值

交换字符串中的元素

冗余连接

移除最多同行列的石头

打砖块

账户合并

连接所有点的最小费用

1319. 连通网络的操作次数

由斜杠划分区域

1579. 保证图可完全遍历

1631. 最小体力消耗路径

839. 相似字符串组

发表评论

表情：
评论列表 （有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

    相关 并查集详解

    讲并查集之前，先给大家一个并查集模板的题目； [题目链接][Link 1] 最简单版的并查集 之前看别的blog的时候，看到过一个有趣的比喻，假设开始的每个人都自立

    朱雀朱雀/ 0 赞/ 154 阅读

    相关 并查集详解 (转)

    并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。（party：我靠，关我

    谁践踏了优雅谁践踏了优雅/ 0 赞/ 216 阅读

    相关 并查集详解

    并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。（party：我靠，关我

    我就是我我就是我/ 0 赞/ 199 阅读

    相关 并查集详解

    这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧 并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

    桃扇骨桃扇骨/ 0 赞/ 234 阅读

    相关 并查集详解

    来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的

    Dear 丶Dear 丶/ 0 赞/ 229 阅读

    相关 并查集实现

    并查集是什么东西？ 它是用来管理元素分组情况的一种数据结构。 他可以高效进行两个操作： 1. 查询a，b是否在同一组 2. 合并a和b所在的组 萌新可能不知所云，这

    深碍√TFBOYSˉ_深碍√TFBOYSˉ_/ 0 赞/ 195 阅读