Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components?（图论+连通块+bfs）

题目链接

题意：给定一个完全图，让你删去m条边后，剩下的连通块个数和每个连通块的大小
思路：可以bfs将属于同一个连通块集的元素放在一起，知道v为空，v是所有的顶点集。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+1;
map<int,int>p[maxn];
vector<int>v,ans;
int bfs(int x)
{
	queue<int>q;
	q.push(x);
	int cnt=0;
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		cnt++;
		for(int i=0;i<v.size();++i)
		if(!p[top][v[i]])
		{
			int x=v[i];
			q.push(v[i]),swap(v[i],v.back()),v.pop_back(); 
			i--;
		}
	}
	return cnt;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),p[u][v]=p[v][u]=1;
	for(int i=1;i<=n;++i) v.push_back(i);
	while(v.size()>0)
	{
		int x=v.back();
		v.pop_back();
		ans.push_back(bfs(x));
	}
	printf("%d\n",ans.size());
	sort(ans.begin(),ans.end());
	for(auto i:ans) printf("%d ",i);
 }