每日消息!【并查集】连通块中的数量

2023-02-16 11:14:38 来源：博客园

(资料图片仅供参考)

导读 ^ _ ^

并查集可以高效解决集合查询和合并操作。当遇到需要判断所属关系的问题时，记得想到并查集。

什么是并查集

高效解决集合查询和合并的数据结构

原始任务：1、将两个集合合并。2、询问两个元素是否在一个集合当中，近乎O(1)O(1)时间内支持两个操作。基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]]表示x的父节点

如何判断树根？if(p[x]==x)
如何求xx的集合编号？find(x)
如何合并两个集合?p[find(a)] = find(b)

优化方式

路径压缩。

额外信息

我们可以通过一些辅助手段，从而使得并查集可以维护更多的信息。具体可以看下面题目。

连通块中的数量

思路

在原来合并的查找合并的基础上。加入size数组来维护其大小。

代码实现

#include#includeusing namespace std;const int N = 100010;int p[N],size[N]; // p记录父节点，size记录大小int n,m;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; size[i] = 1;  }  while(m--) {    int a,b;    char op[5];    scanf("%s",op);        if(op[0] == "C" ) {      scanf("%d%d",&a,&b);      if(find(a) == find(b)) continue;//记得特判      size[find(b)] += size[find(a)];      p[find(a)] = find(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",size[find(a)]);    }  }  return 0;}

#谢谢你的观看！

^ _ ^

关键词：额外信息数据结构的基础上