Codeforces #599 Div1 B. 0-1 MST

似たようなのどっかで見てそう。
https://codeforces.com/contest/1242/problem/B

問題

完全グラフが与えられる。
ほとんどの辺の長さは0で、一部1である。
MSTの辺の重さの総長を求めよ。

解法

未処理の点から順に処理していく。
同じく未処理の点のうち、距離が1でないものを貪欲に取り込み連結しよう。
長さが1の辺は少ないので、ほとんどの頂点がすぐ連結される。

int N,M;
set<int> S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		S[x-1].insert(y-1);
		S[y-1].insert(x-1);
	}
	queue<int> L;
	FOR(i,N) L.push(i);
	
	int num=0;
	while(L.size()) {
		x=L.front();
		L.pop();
		num++;
		queue<int> Q;
		Q.push(x);
		
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			queue<int> L2;
			while(L.size()) {
				r=L.front();
				L.pop();
				if(S[x].count(r)) {
					L2.push(r);
				}
				else {
					Q.push(r);
				}
			}
			swap(L,L2);
		}
	}
	cout<<num-1<<endl;
}

まとめ

どこで見たんだったかなぁ。