并查集

基础并查集

（tips：求最小生成树的Kruskal算法也需要用到并查集。）

查询操作

下面是并查集的几种实现方式。

递归版本：

int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}

可以精简为一行：

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);//意思是如果x等于fa[x]就返回值x，否则将find(fa[x])赋值给fa[x]后返回值fa[x]
}

while循环版本：

int find(int x){
    while(x!=fa[x])x=fa[x]=fa[fa[x]];
    return x;
}

由于省去了调用函数的环节，这个写法相比递归版速度会更快，不过两者相差不大。

合并操作：

void merge(int x,int y){
    int xx=find(x),yy=find(y);
    fa[xx]=yy;
}

将两个元素归为一个集合中。

例题

P1551 亲戚

P1536 村村通

P2814 家谱（需要使用哈希或map）

种类并查集

同时维护多个种类的关系。

例如你需要维护朋友和敌人这两个关系，我们可以将普通并查集的范围扩大至两倍，1_{n用来维护朋友关系，n+1}2n用来维护敌人关系，然后根据题意加以操作即可。

下面给出实现以上操作的部分代码。

int n,m;//n个人，m个关系
int fa[N<<1];//N<<1是位运算，相当于N*2
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n<<1;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int op,x,y;//op为操作类型
        cin>>op>>x>>y;
        if(op==1){//两人为朋友关系
            fa[find(x)]=find(y);//合并操作
        }
        else{//两人为敌人关系
            fa[find(x+n)]=find(y);//朋友的敌人和敌人是同类
            fa[find(y+n)]=find(x);//敌人的敌人和朋友是同类
        }
    }
}

例题

P1892 [BOI2003] 团伙

P2024 [NOI2001] 食物链（需要维护三个种类关系）

P1525 [NOIP2010 提高组] 关押罪犯（也可以用二分图判断来做）

P1955 [NOI2015] 程序自动分析（数据范围较大，需要使用离散化或哈希）

带权并查集

额外维护两个数组d和siz，d用来记录当前节点到其父亲节点的距离，siz用来记录祖宗节点所在集合中的节点个数。

在路径压缩的同时更新d数组来统计节点到根的路径信息。

查询操作：

int find(int x){
    if(x==fa[x])return x;
    int xx=find(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=xx;
}

合并操作：

void merge(int x,int y){
    int xx=find(x),yy=find(y);
    if(xx==yy)return;
    fa[xx]=yy;
    d[xx]+=siz[yy];
    siz[yy]+=siz[xx];
}

初始化：

for(int i=1;i<=n;i++){
    fa[i]=i;
    d[i]=0;
    siz[i]=1;
}

注意一些细节。当我们需要求某点到根节点距离时，需要调用一次find函数进行路径压缩，否则求出的值可能并非之前操作更新后的真实值（详见洛谷P5092）。

拓展

我们考虑以下情况：

给定\(n\)个变量 \(a_1\)~\(a_n\)，m个约束，每个约束形如（\(x,y,c\)）表示 \(a_x-a_y=c\)，判断是否存在可行解。

解法1

将每个约束拆成 \(a_x-a_y\ge c\) 和 \(a_x-a_y\le c\)，使用查分约束。

但是有可能被数据卡到 \(O(nm)\)。

解法2

使用带权并查集。

可以在线性的时间内解决该问。

对于每个约束（\(x,y,c\)），分两种情况考虑：

若 \(x\) 和 \(y\) 不在同一连通块内，从 \(x\) 向 \(y\) 连一条权值为 \(c\) 的边。
若 \(x\) 和 \(y\) 在同一连通块内，只要判断（ \(x\) 到根路径权值和）减去（ \(y\) 到根路径权值和）是否为 \(c\) 即可。

此时的合并操作变为：

 void merge(int x,int y,int c){
     int xx=find(x),yy=find(y);
     if(xx==yy)return;
     fa[xx]=yy;
     d[xx]=d[y]-d[x]+c;
 }

当数据范围过大或维护种类过多导致所需空间较大时，我们可以使用权值并查集来维护种类关系。

例如洛谷P2024，对于每句话中的 \(i\) 和 \(j\) ：

如果 \(i\) 和 \(j\) 不在同一集合（合并操作）：

如果 \(i\) 和 \(j\) 为同类，则从 \(i\) 向 \(j\) 连一条权值为 \(0\) 的边；
如果 \(i\) 是 \(j\) 的天敌，则从 \(i\) 到 \(j\) 连一条权值为 \(1\) 的边；
如果 \(i\) 是 \(j\) 的猎物，则从 \(i\) 到 \(j\) 连一条权值为 \(2\) 的边。

如果 \(i\) 和 \(j\) 在同一集合（询问操作）：

如果 \(i\) 和 \(j\) 是同类，则 \(d_x=d_y\) 时为真话，反之为假话；
如果 \(i\) 是 \(j\) 的天敌，则 \((d_x-d_y+3)\%3=1\) 时为真话，反之为假话；
如果 \(i\) 是 \(j\) 的猎物，则 \((d_x-d_y+3)\%3=2\) 时为真话，反之为假话。

（本题并不需要” \(i\) 是 \(j\) 的猎物“这样的操作，写上是为了能够更好地理解）

（先 \(+3\) 再对 \(3\) 取模是为了防止出现负数，对判断产生干扰）

由于我们维护的是三个种类的关系，这里我们需要对查询操作和合并操作加以修改：

int find(int x){
    if(x==fa[x])return x;
    int xx=find(fa[x]);
    d[xx]=(d[xx]+d[fa[x]])%3;
    return fa[x]=xx;
} 
void merge(int x,int y,int c){
     int xx=find(x),yy=find(y);
     if(xx==yy)return;
     fa[xx]=yy;
     d[xx]=(d[y]-d[x]+c+3)%3;
 }

实际上只是多了一个对权值的取模操作，其他不变。

为方便读者更好地理解以上内容，这里给出一份代码供大家调试。

P2024 带权并查集代码

例题

P1196 [NOI2002] 银河英雄传说

P5092 [USACO04OPEN] Cube Stacking

P2024 [NOI2001] 食物链

by loynyng_fasfy