Codeforces ECR #050 : G. Sources and Sinks

コードは短くても、こりゃ思いつかないな。
http://codeforces.com/contest/1036/problem/G

問題

DAGを成すグラフが与えられる。
入る辺が無い点をsource、出る辺が無い点をsinkと呼ぶことにする。
与えられるグラフはsourceとsinkの数が等しい。

sourceとsinkを1:1でペアを組み、sinkからsourceに辺を張ることを考える。
どのようなペアの組み方であっても、グラフ全体が連結になるかどうか判定せよ。

解法

sourceでもsinkでもない点は、どこかのsourceから来てどこかのsinkに行くパス上に乗ることになるので、結局sourceとsinkが連結になればグラフ全体が連結となる。

条件を満たさないケースを考える。
sourceの部分集合Xのうち、空でもなくsource全体でもないケースを考える。
Xから遷移可能なsinkの集合をf(X)とする。

X

≧

f(X)

の場合、いったんXの範囲に移動してしまうと、以後Xの外のsourceには出られないことになる。

これは明らかに条件を満たさない。
逆に|f(X)|＞|X|ならばX以外のsourceに至る経路が１つはあることになる。

そこで、まず各sourceに対し遷移可能なsinkの集合を求めよう。
次にXを総当たりし、|X|＜|f(X)|を判定すればよい。

int N,M;
vector<int> E[1010101];
vector<int> src,sink;
int in[1010101],out[1010101];
int reachable[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[y-1].push_back(x-1);
		in[y-1]++;
		out[x-1]++;
	}
	
	FOR(i,N) {
		if(in[i]==0) src.push_back(i);
		if(out[i]==0) sink.push_back(i);
	}
	
	FOR(i,sink.size()) {
		queue<int> Q;
		Q.push(sink[i]);
		reachable[sink[i]] |= 1<<i;
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			
			FORR(e,E[x]) if((reachable[e]&(1<<i))==0) {
				reachable[e] |= 1<<i;
				Q.push(e);
			}
		}
	}
	
	for(int mask=1;mask<(1<<src.size())-1;mask++) {
		int tmask=0;
		FOR(i,src.size()) if(mask&(1<<i)) tmask |= reachable[src[i]];
		if(__builtin_popcount(mask) >= __builtin_popcount(tmask)) return _P("NO\n");
	}
	return _P("YES\n");
	
}

まとめ

この考え方は思いつかないなぁ…。