并查集

模板：

int h[N];
for(int i = 0; i < n ; i++)
	h[i] = i; //初始化

int find(int x)//查找+路径压缩
{
	if(h[x] == x) return x;
	return h[x] = find(h[x]);
}

带权并查集

普通的并查集只能维护每个节点所在集合的编号，带权并查集则可以维护集合内任意一点到所在集合根的距离。

简单来说，带权并查集支持如下两种操作：

• 在点 u 和 v 之间连一条边权为 w 的边（u,v 在不同的连通块内）。
• 查询点 u 与该连通块的根（即并查集的根）的距离。

find

int find(int x)
{
    if (f[x] == x)
        return x;
    int fa = find(f[x]);//先保存下来父节点
    dis[x] += dis[f[x]];//把到父结点的距离加上父节点到上个结点的距离
    return f[x] = fa;//合并
}

f[x]：点 x 的父亲节点。

dis[x]：点 x 到其 父亲节点（注意不是根节点）的距离。

请一定注意 dis 数组的定义，如果我们要询问 x 到根路径的权值和，只需要先调用一遍 find 函数（由于使用了路径压缩，此时 x 的父亲就为并查集的根）即可。

merge

void merge(int x, int y, int c)
{
    int fx = find(x), fy = find(y);
    if (fx == fy)
        return;
    f[fx] = fy, dis[fx] = c + dis[y] - dis[x];
}

merge(x, y, c)：在点 x 和点 y 直接连一条权值为 c 的边，同时将 x 所在的连通块合并到 y 上。

例题：洛谷P1525

扩展域并查集

本人认为可以用带权并查集来替代

但是扩展域并查集是对每个结点i，规定i+n为其对立结点（虚拟的）,以此来确定关系。