并查集（Union-Find）

并查集是一种树型的数据结构，它的特点是由 子结点 找到 父结点，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

并查集通过一个一维数组来实现，其本质是维护一个森林。并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)。

求解无向图的所有连通子图 https://blog.csdn.net/wangyibo0201/article/details/51998273

DFS、BFS、并查集。找连通子图，DFS 对所有结点遍历一遍，而用并查集则需要遍历两遍。

并查集的最终结果是生成一个森林，很容易判断图中任意两个节点是否连通，同时也可以求解出所有连通子图。

首先，将所有连通的结点，都放到一起，最终分成几个连通分量组；
其次，用字典存放所有结点所对应的连通分量组号，那么再对原有的图遍历一遍，从字典中查出结点所属的组并且根据组进行区分，就可以得到所有连通子图。

1、把结点编号当做组号。
扫描整个图，一条边任选一个结点编号作为这条边上两个结点的组号；如果字典中已经有了结点的组号，那么选择字典中的。

2、找组号的组号，直到找到祖先。
第一步初始化字典，包括每一个结点。再次遍历字典，对每个结点的组号再次进行寻找组号的操作，直到得到的组号是它自己。

def find(key):
    while parent[key] != key:  
        key = parent[key]
    return key

3、压缩路径

def find(key):
    while parent[key] != key:  
        parent[key] = parent[parent[key]]  
        key = parent[key]
    return key

4、合并结点

def init(key):
    if key not in parent:
        parent[key] = key

def join(key1, key2):
    p1 = find(key1)
    p2 = find(key2)
    if p1 != p2:
        parent[p2] = p1

当我们对图的边进行遍历时，就先执行 init，看节点是否有组号，没有组号就赋值为自己。再执行 join，合并边上的两个节点为同一个组。
　　
最终的结果，一个森林，包括两棵树，每棵树代表连通子图，树中结点的父结点代表自己的组号。

class UnionSet(object):
    def __init__(self):
        self.parent = {
    }

    def init(self, key):
        if key not in parent:
            self.parent[key] = key

    def find(self, key):
        self.init(key)
        while self.parent[key] != key:  
            self.parent[key] = self.parent[self.parent[key]] 
            key = self.parent[key]
        return key      

    def join(self, key1, key2):
        p1 = self.find(key1)
        p2 = self.find(key2)
        if p1 != p2:
            self.parent[p2] = p1

除了求图的连通子图（连通分量）可以用到并查集外，在用 Kruskal 方法求图的最小生成树，也用到了并查集。

1、字典存储

并查集使用的是字典来存储树，字典的键是子结点，值是父结点。

class UnionFind:
    def __init__(self):
       # 记录每个结点的父结点
        self.father = {
    }
       # self.value = {} 如果边有权重 # key 本结点名称 ，value 为本结点 到 根结点的权值

2、添加元素

当把一个新结点添加到并查集中，它的父结点应该是空。

def add(self,x):
	# 添加新结点
	if x not in self.father:
		self.father[x] = None

3、合并两个结点

合并联通的结点，如果属于一棵同树，则任选一个结点作为另一个结点的父结点。如果他们的根是不同的，则让一个树的根结点作为另一个树的根结点的父结点。

def merge(self,x,y):
	''' 合并两个结点 '''
	root_x, root_y = self.find(x), self.find(y) # 查找结点 x，y 的根结点
	if root_x != root_y:   # 根结点不同，则合并
		self.father[root_x] = root_y

4、查找一个结结点的根结点

查找一个根结点的方法是：如果结点的父结点不为空，那么就不断迭代。

def find(self,x):
	root = x
	while self.father[root] != None:
		root = self.father[root]
	return root

5、路径压缩

如果我们树很深，比如说退化成链表，那么每次查询的效率都会非常低。所以我们要做一下路径压缩。也就是把树的深度固定为二。

路径压缩可以用递归，也可以迭代。这里用迭代的方法。

def find(self,x):
	root = x
	while self.father[root] != None:
		root = self.father[root]
	#路径压缩
	while x != root:
		original_father = self.father[x]
		self.father[x] = root
		x = original_father
	return root

6、两结点是否连通

我们判断两个结点是否处于同一个连通分量的时候，就需要判断它们的根结点（祖先）是否相同。

def is_connected(self,x,y):
	return self.find(x) = self.find(y)

并查集 Python 代码的实现

class UnionFind:
    def __init__(self):
        self.father = {
    }
        # self.value = {} 如果边有权重 # key 本结点名称 ，value 为本结点 到 根点的权值

    def add(self,x):
        if x not in self.father:
            self.father[x] = None

    def merge(self,x,y,val):      
        root_x,root_y = self.find(x),self.find(y) #查找结点x，y的跟根结点
        if root_x != root_y:
            self.father[root_x] = root_y

    def find(self,x):       
        root = x
        while self.father[root] != None:
            root = self.father[root]
        #return root

        #路径压缩，有递归和迭代的方法
        while x != root:
            orginal_father = self.father[x]
            self.father[x] = root
            x = orginal_father
        return root

    def is_connected(self,x,y):        
        return self.find(x) == self.find(y)

547. 省份数量

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i):
            for j in range(n):
                if isConnected[i][j] and j not in vis:
                    vis.add(j)
                    dfs(j)

        n = len(isConnected)
        vis = set()
        ans = 0
        for i in range(n):
            if i not in vis:
                ans += 1
                dfs(i) 

                # q = deque([i])
                # while q:
                # i = q.popleft()
                # for j in range(n):
                # if isConnected[i][j] and j not in vis:
                # q.append(j)
                # vis.add(j)
                
        return ans

class Solution {
    
    public int findCircleNum(int[][] isConnected) {
    
        int n = isConnected.length;
        // 初始化并查集
        UnionFind uf = new UnionFind(n);
        // 遍历每个顶点，将当前顶点与其邻接点进行合并
        for (int i = 0; i < n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    
                if (isConnected[i][j] == 1) {
    
                    uf.union(i, j);
                }
            }
        }
        // 返回最终合并后的集合的数量
        return uf.size;
    }
}

// 并查集
class UnionFind {
    
    int[] roots;
    int size; // 集合数量
    
    public UnionFind(int n) {
    
        roots = new int[n];
        for (int i = 0; i < n; i++) {
     roots[i] = i; }
        size = n;
    }

    public int find(int i) {
    
       if (i == roots[i]) return i;
       return roots[i] = find(roots[i]);
    }

    public void union(int p, int q) {
    
        int rootq = find(p);
        int rootp = find(q);
        if (rootq != rootp) {
    
            roots[rootp] = rootq;
            size--;
        }
    }
}

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:

        def find(i: int) -> int:
            # if parent[i] != i: parent[i] = find(parent[i])
            # return parent[i]
            while parent[i] != i:
                parent[i] = parent[parent[i]]
                i = parent[i]
            return i
        
        def union(i: int, j: int):
            parent[find(i)] = find(j)
        
        n = len(isConnected)
        parent = list(range(n))
        
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        return sum(parent[i] == i for i in range(n))

2316. 统计无向图中无法互相到达点对数

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        vis, ans, tot, size = [False] * n, 0, 0, 0
        def dfs(x: int) -> None:
            nonlocal size
            vis[x] = True
            size += 1
            for y in g[x]:
                if not vis[y]:
                    dfs(y)
        for i in range(n):
            if not vis[i]:
                size = 0
                dfs(i)
                ans += size * tot
                tot += size
        return ans
        
class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            parent[find(x)] = find(y)

        parent = list(range(n))  
        for u, v in edges:
            union(u, v)        
        
        for i in range(n):          # 统一祖先节点：一个连通块压缩为一个点
            parent[i] = find(i)
        
        vals = list(Counter(parent).values())   # 每个连通块的大小
        presum = list(accumulate(vals))    # 连通块大小的前缀和
        ans = 0
        for i in range(len(vals)):
            ans += vals[i] * (n - presum[i])  # 数学关系
        
        return ans

990. 等式方程的可满足性

130. 被围绕的区域

128. 最长连续序列

1020. 飞地的数量

1061. 按字典序排列最小的等效字符串

1101. 彼此熟识的最早时间

1102. 得分最高的路径

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

1168. 水资源分配优化

1202. 交换字符串中的元素

1254. 统计封闭岛屿的数目

1258. 近义词句子

1267. 统计参与通信的服务器

128. 最长连续序列

130. 被围绕的区域

1319. 连通网络的操作次数

1361. 验证二叉树

1391. 检查网格中是否存在有效路径

1489. 找到最小生成树里的关键边和伪关键边

1559. 二维网格图中探测环

1569. 将子数组重新排序得到同一个二叉查找树的方案数

1579. 保证图可完全遍历

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

1627. 带阈值的图连通性

1631. 最小体力消耗路径

1632. 矩阵转换后的秩

1697. 检查边长度限制的路径是否存在

1722. 执行交换操作后的最小汉明距离

1724. 检查边长度限制的路径是否存在 II

1905. 统计子岛屿

1970. 你能穿过矩阵的最后一天

1998. 数组的最大公因数排序

200. 岛屿数量

2003. 每棵子树内缺失的最小基因值

2076. 处理含限制条件的好友请求

2092. 找出知晓秘密的所有专家

2157. 字符串分组

2204. Distance to a Cycle in Undirected Graph

2307. Check for Contradictions in Equations

261. 以图判树

305. 岛屿数量 II

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

399. 除法求值

522. 最长特殊序列 II

684. 冗余连接

685. 冗余连接 II

694. 不同岛屿的数量

695. 岛屿的最大面积

711. 不同岛屿的数量 II

721. 账户合并

737. 句子相似性 II

765. 情侣牵手

778. 水位上升的泳池中游泳

785. 判断二分图

803. 打砖块

827. 最大人工岛

839. 相似字符串组

886. 可能的二分法

924. 尽量减少恶意软件的传播

928. 尽量减少恶意软件的传播 II

947. 移除最多的同行或同列石头

952. 按公因数计算最大组件大小

959. 由斜杠划分区域

990. 等式方程的可满足性

LCP 49. 环形闯关游戏

LCS 03. 主题空间