并查集¶

https://blog.csdn.net/u013480600/article/category/1858379

连通性判断 P1197 [JSOI2008]星球大战 P1783 海滩防御非加权维护 P1525 关押罪犯 P2024 [NOI2001]食物链加权维护 P1196 [NOI2002]银河英雄传说 P2342 [USACO04OPEN]Cube Stacking G

基础并查集¶

两个最主要的功能：

查询元素a和元素b是否属于同一组
合并元素a和元素b所在的组

并查集是利用树形结构实现的，但是采用数组进行模拟。查询采用递归的方法去实现，合并则是根据高度（或秩rank）来进行合并。另外为了保证查询的平均时间复杂度为线性，就需要去防止最坏情况的发生，所以需要路径压缩的操作。

并查集的实现：

int n = 1005;
vector<int> parent(n);
vector<int> rank(n); //树的高度

//初始化
void init()
{
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
}

//查询操作
int find(int x)
{
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}

//合并x和y所属的集合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    //如果x和y所属的集合相同，无需操作
    if (x == y) return;
    //按高度合并
    if (rank[x] < rank[y]) parent[x] = y;
    else {
        parent[y] = x;
        if (rank[x] == rank[y]) ++rank[x];
    }
}

//查询x和y是否属于同一个集合
bool isSame(int x, int y)
{
    return find(x) == find(y);
}

扩展域¶

《挑战程序设计竞赛》的食物链开三倍空间的方法。

带权并查集¶

带权并查集是结点存有权值信息的并查集；当两个元素之间的关系可以量化，并且关系可以合并时，可以使用带权并查集来维护元素之间的关系；带权并查集每个元素的权通常描述其与并查集中祖先的关；带权并查集可以推算集合内点的关系，而一般并查集只能判断属于某个集合。

仅以POJ 1182食物链为例来了解带全并查集的基本操作。

从一个结点x指向另一个结点y，表明x和y有联系，相对关系用r来表示。0表示x和y是同类，1表示x吃y，2表示x被y吃。新开一个名为rela的数组，代表结点之间的关系（relation，不这么命名是因为会和标准库函数名冲突），设x所属的集合的根节点为xRoot，则rela[x]代表x对xRoot的关系。

查询操作。已知x和y存在相对关系，关系从y指向x，并且知道x和根节点xRoot的关系，那么当查询y的时候，按照路径压缩的要求，需要将y的根节点也设为xRoot，并且需要去更新y和根节点的关系，即rela[y]。关系是不会因为经过中间的一些结点（比如x）而改变，设y对x的关系为r，那么应有r + rela[x] = rela[y]。为了始终用0，1，2表示关系，需要对结果取模。那么关键问题来了，r是多少，其实在没有去改变y的根节点之前，y的根节点是x，所以会有原来的r = rela[y]，那么更新的时候需要变动两个：一个是修改根节点，和基础并查集一致，另一个就是修改关系，rela[y] = (rela[x] + rela[y]) % 3。

查询相对关系。如果已知x和y属于同一集合，那么可知x和y的根节点相同，现在想知道x对y的关系。根据图中关系可以得出：r + rela[y] = rela[x]，则r = rela[x] - rela[y]，为了防止r出现负数，那么r = (rela[x] - rela[y] + 3) % 3。

1581135189908

合并操作。现在已经知道x和y属于同一集合，现在需要对两个集合的根节点进行合并，假设是把x的根节点合并到y，修改parent的操作和基础并查集一致。从图中可以得到关系：r + rela[y] = rela[x] + rela[parent[x]]，显然需要更新的是rela[parent[x]]，为了防止出现负数，则有：rela[parent[x]] = (r+ rela[y] - rela[x] + 3) % 3

1581135359925

典型题目¶

邝斌带你飞系列：