【数据结构】并查集1
1.引入
对于一个集合S={a1, a2, …, an-1, an}，我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm，我们希望能够快速确定S中的两两元素是否属于S的同一子集。
举个栗子，S={0，1, 2, 3, 4, 5, 6}，如果我们按照一定的规则对集合S进行划分,假设划分后为S1={1, 2, 4}, S2={3, 6}，S3={0, 5}，任意给定两个元素，我们如何确定它们是否属于同一子集？某些合并子集后，又如何确定两两关系？基于此类问题便出现了并查集这种数据结构。
2.概念
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。
3.作用
并查集可以高效的对元素进行分组（合并在一起），并且能快速的查询两个元素是否属于同一组。
4.基本操作
合并：合并两个集合。join函数
查找：判断两个元素是否在一个集合。find函数
5.过程解释
假如有两个集合，之间的关系可以用下面的图像表示：
一开始，分成两组，1和2是同一组，1和3是同一组，那么有没有什么办法可以将这两组练习起来。我们将1视为2的父级，1可以视为3的父级
这样，我们可以把图片划分成下面这样：
那么如果我们有其他的数据，比如下面的4，5，6这样表示
那么新问题来了，这两个集合如果在一块应该怎么表示呢？很简单，让这两个集合中的‘老大’打一架，谁赢了，谁就是两个集合共同的‘老大’。
假如 编号1 赢了，那么集合应该变成下面这样：
也就1成了所有人的‘老大’
那么也就是形成了一个等级严格的树形结构。
从数据结构上看，我们关注的重点是两个数据之间是否连通。
那么看下面这个例子
对于上面这个图，我们如何界定两个节点之间是否有关系呢？比如下面这两个题：
(1)问：2和3之间是否存在关系？
(2)问：3和7之间是否存在关系？
对于问题(1)，我们从图中可以很明显的看出，2和3之间有关系，因为他们有共同的’老大‘。
对于问题(2), 我们从图中也可以明显的看出，3和7之间没有关系，因为从3开始往上找，发现老大是1，而从7开始找，我们发现老大是4，这两个老大（根节点）不一样，说明没有关系。
在做题中，也就是我们输入每组的对应关系如下，
1 2 1 3 4 5 4 6 6 7
然后询问任意两个数（节点）之间有没有关系?
6.代码实现
（1）初始化
我们用f数组表示父级元素节点，初始化代码如下
int f[100]; //父节点 //初始化 n个元素 void Init() { //使每个元素的根节点是其本身 //即初始时每个元素都是单独的 for(int i=1; i<=n; i++){ f[i]=i; } }’每个节点都是自己的父节点‘
（2）查询操作
查询操作有两种实现方式，一种是递归实现，另一种是非递归实现。
递归实现：
int find(int x){ if(f[x] == x) return x; else return find(f[x]);}一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。
非递归实现：
int find(int x) { while(f[x] != x) { //直到元素的父节点是它本身，表示已经查询到了树的根 x= f[x]; return x; //返回根节点对应的元素 }（3）合并
void merge(int a, int b) { //先找到两个元素对应的根对应的元素 int fa = find(a); int fb = find(b); if(fa==fb) return; else f[fa]=fb; //否则令元素 a的根指向元素 b的根 }合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。