Codeforces #346 Div2. E. New Reform

まんまと引っかかったの自分だけ？
http://codeforces.com/contest/659/problem/E

問題

無向グラフが与えられる。
各辺をどちらかの向きの有向辺にするとき、入次数が0の頂点数を最小化し、その数を答えよ。

解法

二部マッチング問題と見なして解くこともアルゴリズム的にはできるが、頂点数・変数が多いのでTLEする(実際自分はやらかした)。
そこで貪欲解法を取る。

頂点を(向きが未確定の無向辺の)次数の少ない順にソートし、順番に処理する。
次数が正なら、その頂点は無向辺のうち1つを自身に向けた辺とし、有向辺の向きを一つ確定される。
…という処理を最後まで繰り返す。

なお、未処理の頂点の無向辺の次数最小値が2以上であれば、おそらくホールの結婚定理で問答無用で残りの全頂点は入次数を正に出来るはず。

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	
	int ret=0;
	set<pair<int,int>> S;
	FOR(i,N) S.insert({E[i].size(),i});
	while(S.size()) {
		if(S.begin()->first>=2) break;
		if(S.begin()->first==0) {
			ret++;
			S.erase(S.begin());
		}
		else if(S.begin()->first==1) {
			x=S.begin()->second;
			y=*E[x].begin();
			S.erase(S.begin());
			S.erase({E[y].size(),y});
			E[y].erase(x);
			S.insert({E[y].size(),y});
		}
		
	}
	
	cout<<ret<<endl;
	
}

まとめ

他に二部マッチング問題にしてTLEした人いないかな…。