leetcode-go/poj/3660.cow-contest/main.cc

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 500;
const int M = 4500;
const int INF = 0x3F3F3F3F;

bool win[N + 1][N + 1];

int main() {
  int n, m, a, b;
  while (scanf("%d %d", &n, &m) != EOF) {
    memset(win, 0, sizeof(win));
    for (int i = 0; i < m; i++) {
      scanf("%d %d", &a, &b);
      win[a][b] = true;
    }
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) win[i][j] |= win[i][k] & win[k][j];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      int cnt = 0;
      for (int j = 1; j <= n; j++) {
        if (win[i][j]) cnt++;
        if (win[j][i]) cnt++;
      }
      if (cnt == n - 1) ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}