题干:
无向图中给定n个顶点,m条不存在的边(除了这m条边,其余都存在),求图的连通分量,及每个连通分量的大小。
解题报告:
https://codeforces.com/blog/entry/4556
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<unordered_map>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 5e5 + 5;
unordered_map<int,bool> mp[MAX];
vector<int> vv;
vector<vector<int> > ans;
vector<int> bfs(int x) {
vector<int> res;
queue<int> q;
q.push(x);
while(q.size()) {
int cur = q.front();q.pop();
res.pb(cur);
// int up = vv.size();这里不能这样写,因为size是动态的。
for(int i = 0; i<(int)vv.size(); i++) {
int v = vv[i];
if(mp[cur].count(v) == 0) {
swap(vv[i],vv.back());//用来实现set的erase操作,减少常数。
vv.pop_back();//用来实现set的erase操作
i--;
q.push(v);
}
}
}
return res;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1; i<=n; i++) vv.pb(i);
for(int x,y,i = 1; i<=m; i++) {
scanf("%d%d",&x,&y);
mp[x][y]=1;
mp[y][x]=1;
}
while(!vv.empty()) {
int v = vv.back();vv.pop_back();
vector<int> cnt = bfs(v);
ans.push_back(cnt);
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());
for(int i = 0; i<(int)ans.size(); i++) {
printf("%d ",ans[i].size());
for(int j = 0; j<(int)ans[i].size(); j++) {
printf("%d ",ans[i][j]);
}
printf("\n");
}
return 0 ;
}