【算法笔记】并查集

本文主要是介绍【算法笔记】并查集，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

并查集：

杂七杂八

并查集是个很简单的基础数据结构，但是真的很有用。

                       --南外的lqs神仙于国庆节的成外

（现在还依稀记得lqs神仙讲图论和基础数据结构时候的那种……）

（晕圈的感觉）

发现自己已经不会写并查集了……

重新学习吧……

算法和两种优化

并查集是一个能够维护很多个不重叠集合的数据结构

支持两种操作 :

Root 查询元素所处的集合。
Union 合并两个集合。

考虑用树形结构储存集合。

对于每一个集合，根节点就是这个集合的“象征”。

我们对于每一个节点 \(i\) ，有一个指针指向它的父亲节点 \(\text{pa}[i]\) ，代表他是属于集合 \(\text{pa}[i]\)的。

如果这个节点是树根，那么同理，它的 \(\text{pa}[]\) 就是自己本身。

不难发现，我们维护的这个结构实际上是由很多个储存集合的树构成的森林。

那么对于查询操作，我们只需要递归查询它的树根就可以了。

也就是这样的。

int root(int x){
	if(pa[x]!=x){
		return root(pa[x]);//不是树根，递归。
	}
    return pa[x];//已经是树根了
}

那么在最开始的时候，每一个元素都是独立的。

我们考虑这样初始化（也就是让每一个元素都是一个集合）：

    for(register int i=1;i<=n;++i){
        pa[i]=i;
    }

我最开始学的时候有过这样一个想法：
直接用 \(\text{pa}[x]\) 储存 \(x\) 在哪一个集合里面。

但是很快就被否决了……

因为这样子合并的时候会十分麻烦……

后来 lqs 说了一个路径压缩的优化。就是利用了这个的思想。

因为我们只关心的是每个集合的根节点。

所以为什么要去管树的结构呢？

我们又不是在写平衡树……

那么就有一种优化。

比如我们查询节点 \(x\) （蓝色箭头表示我们查询之后递归的那个去向）

可以看到，我们在这中间经过了两个另外的节点。

它们和 \(x\) 都在同一条到 \(\text{root}\) 的链上。

所以我们直接把它们的 \(\text{pa}[]\) 全部指向 \(\text{root}\) 。

like is: （这里的蓝色箭头表示我们把它们的 \(\text{pa}[]\) 全部指向了 \(\text{root}\)）

所以在递归查询的时候顺便赋一个值就可以达到这种效果。

int root(int x){
    if(pa[x]!=x){
        pa[x]=root(pa[x]);//优化
    }
    return pa[x];
}

我们将这种优化称之为 “路径压缩” 。

考虑合并集合的操作。

对于两个集合 \(set_x\) 和 \(set_y\)

我们根据这一条：

如果这个节点是树根，那么,它的 \(\text{pa}[]\) 就是自己本身。

我们不难想到，只要任意的让 \(set_x\) 或者 \(set_y\) 的 \(\text{root}\) 的 \(pa[]\) 指向另外一个集合的 \(\text{root}\) 就好了.

void Union(int x,int y){
	return (void)(pa[root(x)]=root(y));
}

不过这个仍然不是最优的……

考虑这一句话：

只要 任意的 让 \(set_x\) 或者 \(set_y\) 的 \(\text{root}\) 的 \(pa[]\) 指向另外一个集合的 \(\text{root}\) 就好了.

任意？怎么任意？能不能有更优的做法？

有的，这是一种启发式合并。

我们维护每一个集合的元素个数。

然后让元素少的集合的根变成元素大的集合的子节点。

这样子我们只会增加小的集合的查询代价（就是说你要多找一个点（那个大集合的根节点））

那么合并之后的查询代价增加就会小。效率就会更高。

当然我们维护的是一个森林。所以也可以维护他们的深度（优化的东西同理）。

void Union(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry){
        return;
    }
    if(size_[rx]>size_[ry]){//size_维护每一个集合的元素个数/深度。
        pa[ry]=rx;
        size_[rx]+=size_[ry];
    }
    else{
        pa[rx]=ry;
        size_[ry]+=size_[rx];
    }优化
}

这个优化就是“按秩合并”。

不过如果这样子做，开始的时候就要加上

    for(register int i=1;i<=n;++i){
        pa[i]=i;
        size_[i]=i;//维护深度
        //size_[i]=1; //维护个数
    }

例题:

P1955 [NOI2015] 程序自动分析

Description
 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
 考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
 现在给出一些约束满足问题，请分别对它们进行判定。
Input
 输入文件的第1行包含1个正整数t，表示需要判定的问题个数。注意这些问题之  间是相互独立的。
 对于每个问题，包含若干行：
 第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。
 接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。
Output
 输出文件包括t行。
 输出文件的第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。
Sample Input
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
Sample Output
NO
YES
HINT

 在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。

 在第二个问题中，约束条件为：x1=x2,x2=x1。这两个约束条件是等价的，可以被同时满足。

 1≤n≤1000000
 1≤i,j≤1000000000

这道题是一道比较经典的题。

我们可以发现，这道题如果不满足，那么一定会出现：

\(x_i=x_j , x_j\not=x_k,x_k=x_i\)

这种“自相矛盾的”关系。

我们注意到，这里用的 \(=\) 是有传递性的

所以我们只需要把所有 \(=\) 的情况扔到一个并查集里面维护。

然后拿不等于的式子去判断 \(x_i \not= x_j\) 时， \(x_i,x_j\) 在不在同一个集合里就好了。

从这里可以发现，并查集可以维护具有 传递性 的集合关系。

（注意本题数据范围，需要离散）

离散的部分大概是这样子的：

vector<int>v;
int main(){
	for(register int i=1;i<=n;i++){
		scanf("%d%d%d",&x[i],&y[i],&e[i]);
		v.push_back(x[i]);
		v.push_back(y[i]);
	}
	sort(v.begin(),v.end());//排序
	v.erase(unique(v.begin(),v.end()),v.end());//去重
	for(register int i=1;i<=n;i++){
		x[i]=lower_bound(v.begin(),v.end(),x[i])-v.begin()+1;
		y[i]=lower_bound(v.begin(),v.end(),y[i])-v.begin()+1;//取出来
     		//这里是把坐标映射成了它的序号。
	}
}

带权并查集

有的时候题目里面会出现“带边权的元素”，要求你维护这些元素的同时还要维护它们的边权（也可以是由“信息”转化得来的“边权”）。

那么我们维护一个数组 \(d[]\) ，\(d[u]\) 表示 \(u\) 节点到\(pa[u]\) 之间的边权。

在路径压缩的时候，我们同时更新\(d\) ，并且利用路径压缩来统计信息。

这里用一道例题讲解。

银河英雄传说[NOI2002]

有一个划分为N列的星际战场，各列依次编号为1,2,…,N。

有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令，每条指令格式为以下两种之一：

1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。

2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。

输入格式
第一行包含整数T，表示共有T条指令。

接下来T行，每行一个指令，指令有两种形式：M i j或C i j。

其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。

输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：

如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

数据范围
N≤30000,T≤500000
输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2
输出样例：
-1
1

可以看得出来，这里我们很明显是需要维护“边权”的。

这里的 \(d[u]\) 就是战舰 \(u\) 到 \(pa[u]\) 中间所隔的战舰数量。

那么让每条边边权为\(1\)，那么我们 \(root\) 操作的时候维护一下边权和。

然后路径压缩的时候\(d\)就直接更新为 \(u\) 到根的边权和就好了。

Code：

int root(int x){
    if(x!=fa[x]){
        int k=fa[x];
        fa[x]=root(fa[x]);
        dis[x]+=dis[k];
        num[x]=num[fa[x]];
    }
    return fa[x];
}

void Union(int x,int y){
    int r1=root(x),r2=root(y);
    if(r1!=r2){
        fa[r1]=r2;dis[r1]=dis[r2]+num[r2];
        num[r2]+=num[r1];
        num[r1]=num[r2];
    }
}

扩展域并查集

扩展域并查集的思想很简单。

在一个题有多种关系需要维护（而且有不同的可能来传递关系）的时候。

（大部分时候它可以维护需要处理“矛盾”并且维护“不矛盾”的信息的问题）

我们将一个节点拆成几个“域”

比如这一道题：

P2024 [NOI2001] 食物链

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 X 和 Y 是同类。
第二种说法是2 X Y，表示 X 吃 Y 。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话
当前的话中 X 或 Y 比 N 大，就是假话
当前的话表示 X 吃 X，就是假话
你的任务是根据给定的 N 和 K 句话，输出假话的总数。

明显的，这一道题需要传递的东西太多了。

那么考虑对于一个元素，它可能需要维护的有什么信息？

天敌，同类，食物。

扩展域的做法就是对于每一个点拆成三个“域”来维护

比如天敌我们用 \(x_{ene}\) ,同类是 \(x_{sam}\) ，食物是 \(x_{eat}\)

然后有种做法就是用三倍的并查集维护。

\(sam=x\), \(ene=x+n\), \(eat=x+2n\)

当然是在输入的时候维护。

只需要三个变量即可。

（因为并查集维护的时候你拿这个集合的任意元素出来合并都可以达到维护的效果）

然后考虑统计假话个数。

也就是在出现假话的时候++ans

真话那么就合并。

（当然这里要注意很多细节，注意代码的注释即可。）

代码（终于自己写了一遍）：

    for(register int i=1;i<=n*3;++i){
        pa[i]=i;
    }
    for(register int i=1,x,y,op;i<=k;++i){
        cin>>op>>x>>y;
        if(x>n || y>n){
            ans++;continue;
        }
        if(op==1){
            if(query(en(x),y)==true || query(en(y),x)==true) ans++; // false
            // x eat y || y eat x
            // then false;
            else{
                Union(x,y);// x,y same type
                Union(en(x),en(y));// same enemy
                Union(fo(x),fo(y));// same food
            } // true
        }
        else{
            if(x==y){
                ans++;continue;
            }
            if(query(x,y)==true || query(en(x),y)==true) ans++;
            // x,y same type || y eat x .
            // then false;
            else{
                Union(fo(x),y);// x eat y
                Union(en(y),x);// y ate by x 
                Union(fo(y),en(x));// y's food eat x
            }// true
        }
    }
    return printf("%d\n",ans),0;

所以它的本质就是拆成多个值域然后看情况维护（拆点）。

fin.

这篇关于【算法笔记】并查集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程