并查集模板

并查集理论就不过多的阐述了，这个数据结构及其解决的等价类相关的问题应该算是比较简单了。

tips

并查集通常使用数组$static \ \ int[] \ \ p = new \ \ int[LEN]$存储某一节点所属等价类的父节点。即$p[i] == j, 1<=j<=n$时，表示节点$i$的父节点是节点$j$。

对于某一根节点$r$，$p[r]$的值可以有多种形式。

• 可以规定$p[r] \ = \ \ r$的节点为根节点，但这样的规则使根节点并未携带其他任何信息。
• 若我们规定$p[r] \leq 0$表示根节点，那么可以用\abs{p[r]}表示一定的信息。比如该根节点表示的等价类的元素数量。

find

这里的find方法包含了路径压缩。当节点$x$是根节点，或是根节点的直接子结点时，不需要路径压缩，直接返回即可。

• y总说实现了路径压缩就可以近似认为并查集相关方法复杂度为O(1)

• 根节点的直接子结点，不要忘记这一类判断，不然会出错…

static int find(int x) {
    if(p[x] == 0) return x;
    if(p[p[x]] == 0) return p[x];

    p[x] = find(p[x]);
    return r;
}

union

只有当两节点不在同一个等价类中才可以合并。

所以y总没有加if，出错了…

static void union(int u, int v) {
	int a = find(u);
	int b = find(v);
	if(a != b) {
		p[a] = b; 
	}
}