CODE THANKS FESTIVAL 2014 A : F - 順位表

解法に気づけばあっさり。
http://code-thanks-festival-2014-a-open.contest.atcoder.jp/tasks/code_thanks_festival_14_quala_f

問題

N人の参加者がコンテストを行い、1～N位までの順位付けがなされた。
何番の参加者は何番の参加者より順位が上、という(矛盾のない)情報がM個与えられる。

これらの情報と矛盾しない範囲で、１番の参加者の取りうる最高順位を求めよ。

解法

Warshall-Floyd法で誰が誰より上、という情報を伝搬させれば、各参加者より上の順位の人を列挙できる。
１番の参加者より上の順位の人数xを列挙すれば、１番の参加者の順位は(x+1)位となる。

int N,M;
int mat[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>x>>y, mat[x-1][y-1]=1;
	FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y] |= mat[x][i]&&mat[i][y];
	x=0;
	FOR(i,N) x+=mat[i][0];
	cout<<x+1<<endl;
	
}

まとめ

今回はNが小さいし、のでWarshall-Floydにしたけど、DFS等でも良いね。