【数据结构】并查集

目录

一：用途

二：实现    O(1)

三：例题

例题1：集合

例题2：连通图无向

例题3：acwing 240 食物链

---

 

一：用途

1. 将两个集合合并
2. 询问两个元素是否在一个集合当中

二：实现    O(1)

每个集合用一棵树表示，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

1. 问题一：如何判断树根：if(p[x]==x)
2. 问题二：如何求x的集合编码：while(p[x]!=x)       x=p[x];
3. 问题三：如何合并两个集合：px是x的集合编码，py是y的集合编码。p[x]=y      //直接将树y插到树x上作为子树。

(1)朴素并查集：int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：p[find(a)] = find(b);(2)维护size的并查集：   //需要求集合点的数量int p[N], size[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点int find(int x)// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;    size[i] = 1;}// 合并a和b所在的两个集合：size[find(b)] += size[find(a)];p[find(a)] = find(b);(3)维护到祖宗节点距离的并查集：int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点int find(int x){if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;d[i] = 0;}// 合并a和b所在的两个集合：p[find(a)] = find(b);d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

三：例题

例题1：集合

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

 输出样例：

Yes
No
Yes

 

#include<iostream>using namespace std;const int N = 100010;int n, m;
int p[N];    //存储父节点int find(int x)     // 返回x的祖宗节点
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++) p[i] = i;      //初始化while(m--){char op[2];int a, b;cin >> op >> a >> b;if(*op == 'M') p[find(a)] = find(b);    //合并a和belse {if(find(a) == find(b)) cout << "Yes" << endl;else cout << "No" << endl;}}return 0;
}

例题2：连通图无向

给定一个包含 n 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

C a b，在点 a 和点 b 之间连一条边，aa 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b可能相等；
Q2 a，询问点 a所在连通块中点的数量；
输入格式

第一行输入整数 n 和 m。

接下来 m行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,p[N],sizee[N];
//p[]存储每个点 sizee[]存储根节点所拥有的子节点数
//并查集中的find函数
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) {p[i]=i;sizee[i]=1;//每个节点作为根节点 集合中只有自己一个元素}while(m--){char op[3];int a,b;scanf("%s",op);if(op[0]=='C')//连边，就是合并{scanf("%d%d",&a,&b);if(find(a)==find(b)) continue;//在一个集合里 就跳出sizee[find(b)]+=sizee[find(a)];//将节点数加到新根节点数上//例如原来a连通块里有3个节点 b里面有4个节点//a连到b的连通块里 那么b里面现在有7个节点p[find(a)]=find(b);//根节点等于b的根节点}else if(op[1]=='1'){scanf("%d%d",&a,&b);if(find(a)==find(b)) puts("Yes");//在同一个集合else puts("No");}else{scanf("%d",&a);printf("%d\n",sizee[find(a)]);//输出根节点的数}}return 0;	
} 

例题3：acwing 240 食物链