并查集是主要用来解决元素分组的问题，只要出现给定一些元素组成一些不相交集合，然后给出几组某某元素之间存在关系，再询问某某元素是否是同一集合的问题，通常就需要并查集大显神威。
就比如判断两个人是否为亲戚关系。
如果两个人人群之中相视一笑不知是不是远房表亲，此时就要扒关系了，你的爷爷辈是谁，我的爷爷辈是谁，一直找到祖先，才发现我们是远方表亲，于是把酒言欢。
分析一下上边的一套操作，首先我们不知道两个元素是不是同一个集合中的，所以我们要觅根求源，我们的并查集就是这个作用，当然，前边是本来就有亲戚关系的，如果追溯到祖先都没有发现他们的关系，那他们就是茫茫人海相遇的陌生人罢了，当然，并查集是支持给两个元素搞上关系的。
根据他的英文名就能知道，他是合并及查找合为一体的数据结构。
并查集支持两种操作：
- 合并（Union）：合并两个元素所属集合（合并对应的树）
- 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
我们需要先进行初始化，然后再构建出他们的功能。
起始，我们给出一组元素，我们可以用一个数组fa[]来存储每个结点的父节点，一开始，这几个元素没有任何关系，我们先将他们的父节点设为他们自己。
假设有0，1，2，3…n个元素。
int fa[n]; void init(int n) { for (int i = 0; i <= n; i++) { fa[i] = i; } }
要注意，数组中存放的是元素的祖先，如何进行合并操作呢？
我们先来看一看find操作。
int find(int i) { if (fa[i] == i) return i; else return find(fa[i]); }
find操作是查找该元素的祖先，如果该元素的祖先就是他自己，就返回他自己。
再来看一看合并操作。
void union(int i, int j) { int i_fa = find(i); int j_fa = find(j); fa[i_fa] = j_fa; }
如果单单看这两个函数，相信大家不会太明白到底是如何合并的。我们可以用几个示例来看一下。
此时的话，数组就变为这样了，我们可以更加形象的表示数组和元素的对应关系。
然后再合并2，3，此时3的祖先为4，2的祖先为2，就是将2的祖先设置为4。同样，如果合并1，2，就是将1的祖先设置为4。
此时
如果此时查找是否1和5是同一集合，只需要查找他们各自的祖先判断是否相等即可。
但是上述find函数是有缺陷的。
如果我们这样合并呢？
是不是还是觉得没有问题，如果我们再合并(2，1)，合并后该结构就像一个链表一样。
此时如果我们合并（4，5）呢？
我们要寻找4的祖先，此时数组中4位置为3，于是传递3，再次寻找3的祖先，还是不对，直至找到1，1的祖先还是1，然后将1的祖先置为5。
如果继续合并（x，4），x是100时，我们就要向上递归100多次，我们不能直接找到合并数的祖先，需要递归查找好久，这样无疑很是浪费时间。
所以我们可以改进find函数
路径压缩版本，在查找时，将路上的节点的祖先直接指向最终的祖先，而不是通过递归一步一步查找。
int find(int i) { if (i == fa[i])//查找到祖先还是进行返回 return i; else { fa[i] = find(fa[i]);//接收返回值，并将最终的父节点赋值给路上的节点 } return fa[i];//继续传递 }
此时再来进行一次模拟
然后继续递归向下寻找。
返回值为1，此次递归结束后，返回调用该递归函数的位置，可以发现，调用2的位置会接收返回值，然后将2的祖先设置为该返回值。
i等于2的递归函数结束后，返回到上一次的调用，即i等于3的位置。
然后继续返回上一层，将4的祖先也置为1。
这时，想要查找任意一个数字的祖先就可以很快查到。
此时合并4，5，4的祖先为1，5的祖先为5，直接就可以将1的祖先设置为5，不像之前那样需要递归多次。
现在给出一个例题。
题目解析
给出n个顶点，然后给出数组，数组中装的就是顶点和顶点之间的边，我们需要确定在根据数组中保存的边和边的关系，来推断某两个顶点是否相连。
就比如第一个例子
n等于3，就是有3个节点，分别为0，1，2。
如果想要从0到2，我们可以通过1间接到达，也可以直接从0到2，所以返回结果为true。
看第二个例子
正如上图，在将数组中的边连接后，会分成两个模块，但是不存在从0到达5的节点，所以此时返回false。
这道题目就是并查集的经典题目，我们只需要将数组中给出的两两元素连接即可。
使用find和union函数就可以连接，在此之前记得初始化。
class Solution { public: int find(int i) { if (i == fa[i])//查找到祖先还是进行返回 return i; else { fa[i] = find(fa[i]);//接收返回值，并将最终的父节点赋值给路上的节点 } return fa[i];//继续传递 } void Union(int i, int j) { int i_fa = find(i); int j_fa = find(j); fa[i_fa] = j_fa; } int* fa=new int[1000000]; bool validPath(int n, vector<vector<int>>& edges, int source, int destination) { //先初始化 for(int i=0;i<n;i++) { fa[i]=i; } for(auto k:edges) { Union(k[0],k[1]); } if(find(source)==find(destination)) { return true; } return false; } };
