并差集-python版本

偏执的太偏执、 2023-06-12 06:23 5阅读 0赞

# 并差集-python版本 #

## 简介 ##

> 并查集，在一些有N个元素的[集合][Link 1]应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。 --百度百科

## 应用 ##

一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

## 基本操作 ##

### 初始化 ###

并查集的实现原理也比较简单，就是使用树来表示集合，树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表

![dsu示意图][dsu]

图中有两棵树，分别对应两个集合，其中第一个集合为$ \{a,b,c,d\}$，代表元素是  a a a；第二个集合为  \{ e , f , g \} \\\{e,f,g\\\} \{ e,f,g\}，代表元素是  e e e。

树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示其没有父节点。沿着每个节点的父节点不断向上查找，最终就可以找到该树的根节点，即该集合的代表元素。

# parent数组记录该元素父节点的序号，size表示该树高（以根节点计算）
    class DSU:
        def __init__(self, num):
            self.parent = list(range(num))
            self.size = [1] * num

### 查找根节点 ###

通过递归的方式，进行查找该树的根节点。如：find(d) -> a.

![查找根节点][20191031200930495.png]

def find(self, x):
            ''' 查找x的父节点 :param x: :return: '''
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

### 求并集 ###

在并集的时候，通过size数组记录树高，从而进行路径压缩。可以防止极端情况，如查找中的图。

![交集][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTkwNTkz_size_16_color_FFFFFF_t_70]

def union(self, x, y):
            ''' 合并x和y的集合 :param x: :param y: :return: '''
            x_root = self.find(x)
            y_root = self.find(y)
            if x_root == y_root:
                return
            # 根据树高进行计算
            if self.size[x_root] > self.size[y_root]:
                # 将y合并到x
                self.parent[y_root] = x_root
            elif self.size[x_root] < self.size[y_root]:
                self.parent[x_root] = y_root
            else:
                self.parent[x_root] = y_root  # x拼接到y上
                self.size[y_root] = self.size[y_root] + 1

## 参考 ##

[【算法】并查集（Disjoint Set）][Disjoint Set]

[并查集][Link 2]

[924. Minimize Malware Spread][]

[Link 1]: https://baike.baidu.com/item/%E9%9B%86%E5%90%88/2908117
[dsu]: /images/20230531/bbab4e9a11d54a288f615317485ec092.png
[20191031200930495.png]: /images/20230531/884f46e813234d65a64ac6528a092c27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTkwNTkz_size_16_color_FFFFFF_t_70]: /images/20230531/19f0560a892a461ca5b531bd2c8e6b14.png
[Disjoint Set]: https://www.bilibili.com/video/av38498175/?p=1
[Link 2]: https://www.cnblogs.com/cyjb/p/UnionFindSets.html
[924. Minimize Malware Spread]: https://leetcode-cn.com/problems/minimize-malware-spread/