【算法】——并查集

作者：指针不指南吗
专栏：算法篇

🐾或许会很慢，但是不可以停下🐾

1.思想

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）
比如说，我们可以用并查集来判断 某个节点是否属于某棵树等。

• 并查集

  1. 将两个集合合并

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

• 基本原理

  每个集合用一棵树来表示。

  树根的编号就是整个集合的编号。

  每个节点存储它的父节点，p[x]表示x的父节点。

• 相关问题

  1. 如何判断树根：if(p[x]==x)

  2. 如何求x的集合编号：while(p[x]!=x) x=p[x]

  3. 判断两个元素是否在一个集合里面，即两个元素的编号相同：find(p[x])==find(p[y])

  4. 如何合并两个集合：px是x的集合编号，py是y的集合编号。

     p[x]=y，即让一个集合 a 的根节点指向另一个集合 b 的根节点，把a直接插在b的根节点下面。

• 优化

  • 路径压缩：让每个节点都直接指向根节点（祖先）

2.模板

并查集的类型模板这里给出三种，具体题目具体分析，看看需要维护什么，添加什么。

(1)朴素并查集：

int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;  //初始化每个元素的父节点和祖宗节点就是它本身// 合并a和 b所在的两个集合：
p[find(a)] = find(b);   //让a的祖宗节点指向b的祖宗节点，a树插在b根节点下面

(2)维护size的并查集：

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}// 初始化，假定节点编号是1~n
for (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~n
for (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)的偏移量

3.应用

3.1 合并集合

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

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

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

输入格式

第一行输入整数 n 和 m。

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

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤$10^5$

输入样例：

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

输出样例：

Yes
No
Yes

• 代码实现

  #include<bits/stdc++.h>
  using namespace std;const int N=100010;int n,m; //n表示点的数量，m表示操作的次数
  int p[N];  //存的每个节点的父节点int find(int x) //返回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; //最开始，每个点都各自在一个集合中，so父节点就是他本身；while(m--){char op[2];int a,b;scanf("%s%d %d",op,&a,&b);//合并if(op[0]=='M') p[find(a)]=p[find(b)];  //让a的祖宗节点等于b的祖宗节点，让a的祖宗节点直接插在b祖宗节点下面else{if(find(a)==find(b)) puts("Yes");  //判断是否属于同一个集合else puts("No");}  }return 0;
  }
  

注意

读入字母M或者是Q的时候，使用字符串op[2],是因为直接用char的话，可能会出现空格换行的问题作物，这种比较保险，记得在后面使用的时候，用op[0],不能直接使用op

puts自动包含换行

3.2 连通块中点的数量

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

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

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

输入格式

第一行输入整数 n 和 m。

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

输出格式

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

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

每个结果占一行。

数据范围

1≤n,m≤$10^5$

输入样例：

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

输出样例：

Yes
2
3

• 思路

  • 连通块就是一个点的集合：集合中的点可以相互到达，直接或者是间接都是可以的；

  • 这时候我们可以把它类比成一个树，运用并查集，一个点集合，我们可以用一个编号来表示，属于同一个编号，就说明两个点之间可以相互到达，在一个连通块里面；

  • 有三个操作：

    1. 两点之间连一条边，那么这两个点所在集合中的点，都是可以相互到达的，即合成一个连通块，用并查集中的合并操作；

    2. 判断是否在一个连通块，用并查集的查询；

    3. 询问一个点集合的数量，需要我们额外维护，初始化的时候每个集合1个，合并的时候，两个集合数量相加，最后输出即可

• 代码实现

  #include<bits/stdc++.h>using namespace std;const int N=1000010;
  int n,m;
  int p[N],sizel[N];  //p表示父节点，sizel表示集合的大小，记住sizel里面放的是祖宗节点，后面容易出错int find(int n)  //返回祖宗节点
  {if(p[n]!=n) p[n]=find(p[n]);return p[n];
  }int main()
  {scanf("%d%d",&n,&m);  //读入点的数量和操作的次数for(int i=1;i<=n;i++){   //初始化，父节点就是它本身；集合大小都是1，只有他自己p[i]=i;sizel[i]=1;}char op[5];   while(m--){scanf("%s",op);  //读入操作的名字if(op[0]=='C'){   //合并int a,b;scanf("%d%d",&a,&b);if(find(a)==find(b)) continue;  //相同则进入下个循环else{   //不同即操作，两步的顺序不能反！！！sizel[find(b)]+=sizel[find(a)];  //b的集合大小加上a的集合大小p[find(a)]=find(b);   //让a的祖宗节点指向b的祖宗节点}}else if(op[1]=='1'){  //查询是否一个集合int a,b;scanf("%d%d",&a,&b);if(find(a)==find(b))  puts("Yes");else puts("No");}else{if(op[1]=='2') {   //输出集合大小int d;scanf("%d",&d);printf("%d\n",sizel[find(d)]);  }}}return 0;
  }