【CodeForces - 190E】Counter Attack （补图bfs，卡常，dsu）

题干：

无向图中给定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 ;
}