并査集

并査集是一个用于维护**不相交集合（Disjoint Set)**的数据结构。其本质是对每一个元素选定一个“代表元”，且相同集合中元素的“代表元”相同（这个集合的“代表元”就是其中每个节点的代表元）。

注意：这个字读chá$!!!$

并査集可以用于维护具有传递性的信息，一个典型的例子是相等关系(若$a=b$，$b=c$,则$a=c$)（$ps$：恋爱关系很明显不具有传递性$\dots$)

结构

算法竞赛领域的“并査集”一般指树形并查集（并查集的实现还有一种链表形式，但效率非常低下，所以一般不使用）

树形并查集的结构是一个森林，每棵树代表一个集合，其树根就是“代表元”，其结构如图所示：

并查集演示.png

（图中1,2,3号节点构成一个代表元为1的集合，4号节点构成一个代表元为4的集合，5,6,7,8号节点构成一个代表元为5的集合）

由此可以看出，这种并查集的实现只要找到树根就可以判断两个元素是否在一个集合中，效率很高。

并查集的功能通过两个基本操作来实现，即“找根”和“合并”：

首先我们需要存储每个节点的父节点：

1	int fa[maxn] //x的父节点为fa[x]

接下来，对于每个节点，我们只需要沿着“父节点”不断向上寻找，直到找到父节点是自身的节点（树根）

找根.png

比如说对4号节点进行“找根”，因为4号节点的父节点是2号节点，再对2号节点进行“找根”，依此类推。直到找到1号节点，因为1号节点的父节点指向自身，因此可以判定1号节点是树根，即4号的“代表元”。

代码：

int getf(int v)
{
    if(f[v]==v) return v; //如果是根节点，返回
    else return getf(f[v]); //否则找根
}

因为每个集合都由一个“代表元”（树根）指定，所以只要简单地合并两个集合的“代表元”（使一个“代表元”成为另一个“代表元”的子节点），就可以合并两个集合。

代码：

void merge(int a,int b)
{
    int x=getf(a); //a的“代表元”
    int y=getf(b); //b的“代表元”
    if(x==y) return; //a与b在同一个集合中
    f[x]=y; //合并
}

使用上面方式实现的并查集已经可以实现其功能了，但是还存在一个问题：

如果并查集被合并成像上图一样的链式结构，那么对n号节点