参考
https://www.cnblogs.com/asdfknjhu/p/12515480.html
https://www.bilibili.com/video/BV13t411v7Fs?p=3
https://leetcode-cn.com/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/

一、基本概念

并查集是一种数据结构
并查集这三个字，一个字代表一个意思。
并（Union），代表合并
查（Find），代表查找
集（Set），代表这是一个以字典为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素
并查集的典型应用是有关连通分量的问题
并查集解决单个问题（添加，合并，查找）的时间复杂度都是 O(1) O(1) O(1)
因此，并查集可以应用到在线算法中

二、并查集的引入

假设有一个图如下图所示：

问题：我们要判断该图有没有环？
如下图所示红线连接的就是一个环

第一步：将图中6个点平铺写开
在这里插入图片描述第二步：任意从图中的一个边开始，把所有的边都给遍历一遍，首先选择01之间的边，选择边后我们把这条边所连接的两个顶点放到一个集合中，如下图示：
选择12之间的边，选择边后我们把这条边所连接的两个顶点放到一个集合中，1已经在集合中了，只需要把2放进去就可以了。集合的意义是该集合中的元素可以在图中相互走通的（即任意两个元素是直接或者间接相连的）如下图示：

在这里插入图片描述
选择34之间的边，选择边后我们把这条边所连接的两个顶点放到一个集合中，3和4与上一个集合中的元素目前没有连接所以单独放在一个集合中。如下图示：

选择13之间的边，选择边后我们把这条边所连接的两个顶点放到一个集合中，13分别在一个集合中，要让他们在一个集合中就要将13所在的集合合并。如下图示：
在这里插入图片描述
到目前为止我们使用过得边有（0，1）（1，2）（3，4）（1，3），由于我们选边的时候不会重复且边（0,1）和（1,0）是同一条边。如果接下来选边的时候（选边不重复），该边的两个端点出现在同一个集合中，则该集合元素可以构成一个环，即该图是有环的。如选择边24,24在集合中，所以可以构成环，该图有环。如图示：在这里插入图片描述
用代码实现的时候用树的结构来存储上面说的集合。在集合合并的时候如果一个边的两个结点所在的树（存储集合的）的根节点指向另一个树的根节点：

在这里插入图片描述
接下来找到边24 2的根和4的根相同都是4，这说明顶点2和4本身就在集合中（树上）。即有环。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define VERTICES 6
int find_root(int x, int parent[])  // 找到根节点
{int x_root = x;while (parent[x_root] != -1){x_root = parent[x_root];}return x_root;
}
int union_vertices(int x, int y, int parent[])  // 让两个集合合并
{int x_root = find_root(x, parent);int y_root = find_root(y, parent);if (x_root == y_root)return 0;else{parent[x_root] = y_root;return 1;}
}
int main(void)
{int parent[VERTICES] = { 0 };memset(parent, -1, sizeof(parent));   // 初始化int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5} }; // 边集for (int i = 0; i < 6; i++){int x = edges[i][0];int y = edges[i][1];if (union_vertices(x, y, parent) == 0){printf("Cycle detected!\n");system("pause");exit(0);}}printf("No cycle found.\n");system("pause");return 0;
}

三、根据Rank的合并（压缩路径）

为了避免树的构建出现链条形状，影响根的查询，所以在合并的时候让矮树的根节点指向高树的根节点。
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define VERTICES 6
int find_root(int x, int parent[])  // 找到根节点
{int x_root = x;while (parent[x_root] != -1){x_root = parent[x_root];}return x_root;
}
int union_vertices(int x, int y, int parent[],int rank[])  // 让两个集合合并
{int x_root = find_root(x, parent);int y_root = find_root(y, parent);if (x_root == y_root)return 0;else{if (rank[x_root] > rank[y_root])  // 让 少的指向多 的{parent[y_root] = x_root;}else if (rank[x_root] < rank[y_root])parent[x_root] = y_root;else{parent[x_root] = y_root;   // 这个随便可以rank[y_root]++;}return 1;}
}
int main(void)
{int parent[VERTICES] = { 0 };int rank[VERTICES] = { 0 };memset(rank, 0, sizeof(rank));memset(parent, -1, sizeof(parent));int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5} };for (int i = 0; i < 6; i++){int x = edges[i][0];int y = edges[i][1];if (union_vertices(x, y, parent,rank) == 0){printf("Cycle detected!\n");system("pause");exit(0);}}printf("No cycle found.\n");system("pause");return 0;
}

python并查集模板分析

一、并查集的实现

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,val):"""合并两个节点"""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 = xwhile self.father[root] != None:root = self.father[root]return root

在这里插入图片描述

5、路径压缩

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

这么做可行的原因是，并查集只是记录了节点之间的连通关系，而节点相互连通只需要有一个相同的根节点（祖先）就可以了。

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

    def find(self,x):"""查找根节点路径压缩"""root = xwhile self.father[root] != None:root = self.father[root]# 路径压缩while x != root:original_father = self.father[x]self.father[x] = rootx = original_fatherreturn root

路径压缩的时间复杂度为O(log⁡∗n)O(\log^*n)O(log∗n)
log⁡∗n\log^*nlog∗n 表示 n 取多少次log⁡2n\log_2nlog2n并向下取整以后变成 1
可以认为O(log⁡∗n)=O(1)O(\log^*n) = O(1)O(log∗n)=O(1),因为log⁡∗265536=5\log^*2{65536} = 5log∗265536=5，而2655362^{65536}265536是一个天文数字。这个时间复杂度当成结论记下就可以。
在这里插入图片描述

6、两节点是否连通

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

def is_connected(self,x,y):"""判断两节点是否相连"""return self.find(x) == self.find(y)

完整模板

class UnionFind:def __init__(self):"""记录每个节点的父节点"""self.father = {}def find(self,x):"""查找根节点路径压缩每一次查找节点x的根节点的时候都对该节点进行路径压缩"""root = xwhile self.father[root] != None:root = self.father[root]# 路径压缩while x != root:original_father = self.father[x]self.father[x] = rootx = original_fatherreturn rootdef merge(self,x,y,val):"""合并两个节点"""root_x,root_y = self.find(x),self.find(y)if root_x != root_y:self.father[root_x] = root_ydef is_connected(self,x,y):"""判断两节点是否相连"""return self.find(x) == self.find(y)def add(self,x):"""添加新节点"""if x not in self.father:self.father[x] = None