[2458] 키 순서

// 2458 키 순서  
#define INF 100 * 100000 + 1
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int dist[501][501];
int N, M, a, b, c;

// static 함수로 빼야 속도가 빠르다.
// main 함수 내에 구현하지 말 것!
void floyd() {
    // 꼭 k 를 가장 바깥쪽 for 루프에서 돌려야 정답이 나온다. 안쪽에 있으면 오답
    for (int k = 1; k <= N; k++) { //
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // i -> j 바로 가는 거리보다
                // i -> k 로 가고 k -> j 로 가는 거리가 더 짧다면 갱신한다.
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// N: 학생의 수 2 ~ 500 -> 시간복잡도O(N^3) -> N이 작은게 힌트  
	// M: 비교횟수 1 ~ N(N-1)/2 
    scanf("%d %d", &N, &M); 

	// 초기화  
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if(i == j) {
                dist[i][j] = 0; // 동일한 정점까지 거리는 0으로 설정
            } else {
                dist[i][j] = INF; // 무한대 값으로 초기화
            }

        }
    }

    for (int i = 0; i < M; i++) {
        // 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
        // 동일한 노선이 여러개면 비용이 작은 값만 들고 있으면 된다.
        scanf("%d %d", &a, &b);
        dist[a][b] = min(dist[a][b], 1); // 
    }

    floyd();

	int ans = 0;
    for (int i = 1; i <= N; i++) {
    	int cnt = 0;
        for (int j = 1; j <= N; j++) {
        	if (i==j) continue;
        	if(dist[i][j] != INF || dist[j][i] != INF){
        		cnt++;
			}
        }
        if(cnt== N-1) ans++;
    }
    printf("%d", ans);
    
    return 0;
}