백준 2458 키 순서

문제 : https://www.acmicpc.net/problem/2458

#include <iostream>
#define INF 987654321
using namespace std;

int N, M;
int tall[501][501];

void input(){
  cin >> N >> M;
  for(int i = 0; i <= N; i++){
    for(int j = 0; j <= N; j++){
      tall[i][j] = INF;
    }
  }
  
  for(int i = 0; i < M; i++){
    int a, b;
    cin >> a >> b;
    tall[a][b] = 1;
  }
}

void floyd(){
  for(int k = 1; k <= N; k++){
    for(int i = 1; i <= N; i++){
      for(int j = 1; j <= N; j++){
        if(tall[i][j] > tall[i][k] + tall[k][j] ){
          tall[i][j] = tall[i][k] + tall[k][j];
        }
      }
    }
  }
}

void output(){
  int ans = 0;
  for(int i = 1; i <= N; i++){
    int cnt = 0;
    for(int j = 1; j <= N; j++){
      if(tall[i][j] != INF || tall[j][i] != INF){
        cnt++;
      }
    }
    if(cnt == N-1) ans++;
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  floyd();
  output();
  return 0;
}