CROC 2016 Elimination Round : D. Robot Rapping Results Report

Cで二分探索使ったおかげで、2問連続二分探索になっちゃった。
http://codeforces.com/contest/655/problem/D

問題

N個のロボットが、1対1の試合を計M試合行った。
各試合の記録として、U[i]番のロボットがV[i]番のロボットに勝ったことが分かっている。

ロボットの強弱関係は推移律を満たすことが分かっている。
試合の記録に対して、全ロボットの順位が一意に決まるには、最小で先頭何試合分の記録があればよいか。

解法

試合数mに対し二分探索を行う。

全ロボットの順位が一意に決まるには、m試合の強弱関係から構成される有限グラフに対してトポロジカルソートを用いてロボットを順次処理する際、選択対象の点が常に１個しかないかどうかを判定すればよい。
ソート途中で入次数が0の頂点が2個以上ある場合は順位が一意に定まらないと言えるので不可。

int N,M;
int U[101010],V[101010];
vector<int> E[101010];
int fix[101010],in[101010];

int ok(int S) {
	int i;
	S=min(S,M);
	FOR(i,N) E[i].clear();
	ZERO(in);
	FOR(i,S) E[U[i]].push_back(V[i]), in[V[i]]++;
	
	int left=N;
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	
	while(Q.size()) {
		if(Q.size()>1) return 0;
		left--;
		int x=Q.front();
		Q.pop();
		FORR(r,E[x]) if(--in[r]==0) Q.push(r);
	}
	
	return left==0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>U[i]>>V[i], U[i]--, V[i]--;
	
	int ret=1<<20;
	for(i=19;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
	
	if(ret>M) ret=-1;
	cout<<ret<<endl;
}

まとめ

Dが恐らく二分探索が想定解だとすると、Cの想定解は二分探索じゃなかったのかな？