POJ 3660 Cow Contest

解法

入力から有向グラフを作る。AがBに勝ったという情報からA -> Bに辺を張る
このグラフ上でiからjに到達可能ならば、iはjに勝てる

n cows中でiがkthの時、iは(n - k)cowsにwin and iは(k - 1)cowsにlose
順位が決定できる場合、win + lose == (n - k) + (k - 1) == n - 1となる

ソースコード

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    bool e[128][128];
    CL(e, 0);
    while (m--)
    {
	int a, b;
	scanf("%d%d", &a, &b);
	--a, --b;
	e[a][b] = true;
    }
    rep(k, n) rep(i, n) rep(j, n)
	e[i][j] |= e[i][k] && e[k][j];

    int win[128] = {}, lose[128] = {};
    rep(i, n)
	rep(j, n)
	    if (e[i][j])
		++win[i], ++lose[j];

    int res = 0;
    rep(i, n)
	if (win[i] + lose[i] == n - 1)
	    ++res;
    printf("%d\n", res);
}