[ABC284C] Count Connected Components 题解

FFTotoro · 2023-01-14 18:06:49 · 题解

本题要求求出一个图中连通分量的数量。

本篇题解与其他题解不同，主要介绍 AtCoder Library 中 dsu（并查集）的使用方法。

ACL 中的 dsu 有如下几个函数可供调用：

• void merge(int u,int v)：将两个整数 u 和 v 合并到同一个集合；
• bool same(int u,int v)：判断 u 和 v 是否在同一集合内；
• int leader(int u)：返回 u 所在集合的祖先；
• vector<vector<int> > groups()：返回所有集合，每个子 vector 代表一个集合，里面包含了该集合内的所有元素。

每次连边就相当于合并两个数所在的集合。最终的答案就是 groups().size()，即集合的个数。

放代码：

#include<atcoder/all>
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  atcoder::dsu d(n);
  while(m--){
    int x,y; cin>>x>>y;
    d.merge(x-1,y-1); // 合并
  }
  cout<<d.groups().size()<<endl; // 集合数即为连通分量数
  return 0;
}