Codeforces ECR #037 : E. Connected Components?

なんかどこかで見たような問題。
http://codeforces.com/contest/920/problem/E

問題

N頂点の完全グラフからM辺を取り除いたものが与えられる。
連結成分は何個か、そして各連結成分内の頂点数はいくつか。

解法

未処理の頂点集合を考える。
ここから1個取り出し、連結成分となる頂点をDFSで探索しよう。
1個取り出した時点で残された未処理の頂点をDFSでたどっていく。

int N,M;
set<int> E[202020];
set<int> liv;
vector<int> V;
int ret;

void dfs(int cur) {
	ret++;
	int nex=-1;
	liv.erase(cur);
	
	while(liv.size()) {
		auto it=liv.lower_bound(nex);
		if(it==liv.end()) break;
		nex=*it;
		if(E[cur].count(nex)==0) dfs(nex);
		nex++;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) liv.insert(i);
	FOR(i,M) {
		cin>>x>>y;
		x--;y--;
		E[x].insert(y);
		E[y].insert(x);
	}
	
	while(liv.size()) {
		ret=0;
		dfs(*liv.begin());
		V.push_back(ret);
	}
	sort(ALL(V));
	_P("%d\n",V.size());
	FOR(i,V.size()) _P("%d%c",V[i],(i+1==V.size())?'\n':' ');
}

まとめ

コードは割と単純になるんだよね。