并查集.md

并查集

Union-Find 算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点 union、判断两个节点的连通性 connected、计算连通分量 count 所需的时间复杂度均为 O(1)。

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = totalNodes
        # 连通分量大小，即树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	# 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count

题目

一、只使用图的连通性，或求连通分量数：

130. 被围绕的区域

200. 岛屿的个数

419. 甲板上的战舰（与200题类似）

695. 岛屿的最大面积

$323.无向图中连通分量的数目

$261.以图判树

547.省份数量

684.冗余连接

二、其他问题转换成求连通性：

128. 最长连续序列

990.等式方程的可满足性

三、复杂的路径压缩

399.除法求值

四、最小生成树（后文称mst）

最小生成树，就是图中若干边的集合，你要保证这些边：

1、包含图中的所有节点。

2、形成的结构是树结构（即不存在环）。

3、权重和最小。

用到了贪心思路（Kruskal 算法）：

将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和mst中的其它边不会形成环，则这条边是mst的一部分，将它加入mst集合；否则，这条边不是最小生成树的一部分，不要把它加入mst集合。

求连通所有结点的最少路径之类的问题，就是求树（没有环才能减少路径），并且是最小生成树

复杂度

假设一幅图的节点个数为V，边的条数为E，首先需要O(E)的空间装所有边，而且 Union-Find 算法也需要O(V)的空间，所以 Kruskal 算法总的空间复杂度就是O(V + E)。

时间复杂度主要耗费在排序，需要O(ElogE)的时间，Union-Find 算法所有操作的复杂度都是O(1)，套一个 for 循环也不过是O(E)，所以总的时间复杂度为O(ElogE)。

$1135.最低成本联通所有城市

$1584.连接所有点的最小费用