浅说并查集

简单并查集

作为OI中最为优雅的数据结构，常常被大家拿来赞赏，尽管他的用处不多，但是还是很有必要讲一讲的。
小引

并查集作为一种用于管理元素所属集合的数据结构，他的本质其实就是维护出多棵树，组成一个森林，而其中的每一棵树就是代表的一个集合，而这个树上的的点就代表对应集合中的元素。
既然并查集的本质是树，那么它很显然可以做到两种简单的操作： \(Union\)，\(Find\)。

• \(Unoin\)：合并两个元素他们所在的集合（换句话说就是合并两个树）
  
• \(Find\)：查询某个元素所在的集合（换句话说就是问这个元素在那个树中）
  

那么我们要怎么实现这两个操作呢？
我们先考虑如何判断两个元素是否在同一集合中。
假设我们对每棵树都编一个号，然后设 \(fa\) 表示 \(i\) 号在 \(fa\) 这个集合中，如果说 \(fa==fa[j]\) 是不是就可以说明 \(i\) 和 \(j\) 在同一集合中了？
那么现在的问题就转化成了如何维护这个 \(fa\)。假如说现在我们要让 \(i\) 所在的集合和 \(j\) 所在的集合合并起来，我们可以怎么做？是不是可以让 \(fa=fa[j]\)？显然是错误的！！为啥？因为 \(i\) 所在的集合不只是有 \(i\)，除此之外还有其他的元素，那么这些元素也要改！所以说我们还不如直接暴力改，这样改一次的时间复杂度是 \(\cal O(n)\) 的，那么总共的时间复杂度就是 \(\cal O(n^2)\) 的。
那么还能不能更快一些呢？答案是可以的。
因为我们的每一个集合本质上是用一棵在存储，所以说当一个集合和另一个集合要合并的时候，我们只需要把一棵树的根节点甩到另一个树的根节点的儿子节点就行。

那么此时就是说，对于查询的某一个点，我们就应该一直向上查询，直到查询到真正的根节点为止。那么什么样的点才有资格被评为根节点呢？
如果说我们设刚开始每个点的 \(fa\) 都等于自己，也就是说 \(fa=i\)，那么很显然，当一个点满足 \(fa=i\) 这个条件的时候，他就是一个真正的根节点！
所以说现在的操作就变成了，找到 \(i\) 和 \(j\) 所在集合的根节点 \(root_i\ root_j\)，然后将 \(fa[root_i]=root_j\) 这样是不是就可以了？而且对于下一次找寻的时候，也会找到新的根节点，所以说这样就又可以完成这个操作了！
只不过这里要关注一个点，为了保证时间复杂度降低，我们每一次查询的时候都会更新这个点的根节点，以避免多次查询的时候反复跑路径，从而导致时间复杂度很高。
为什么所这这样的操作方法时间复杂度很低呢？我们可以大致感受一下。
比如说当前的一棵树的深度已经为 \(n-1\) 了，而且树上的最下面的节点是从来没有被更新过的，现在恰好选择了这个节点和最后的一个节点结合，那么在这样的情况下这个点需要跑 \(n-1\) 这么长的路径，同时之前为了把这个树给合并起来，起码也要花 \(n\) 的时间，那么这样算下来的话，总时间复杂度就是 \(\cal O(2\times n)\)，均摊到每一次的话，差不多就是一个常数的大小，所以说时间复杂度是真的非常的低的。
<ul>\(Union\) 模板

1. void merge(int x,int y){
2.     fa[find(x)]=find(y);
3. }

复制代码

\(Find\) 模板

1. int find(int x){
2.     if (fa[x]==x)return x;
3.     else {
4.         fa[x]=find(fa[x]);
5.         return fa[x];
6.     }
7. }

复制代码

初始化模板
[code]for (int i=1;i='0'&&chr;        for (int i=1;iX>>Y>>Z;            if (Z+r>=h){//最上层                up[++cnt1]=i;            }            if (Z-r