[백준] 2458번 : 키 순서

2458번: 키 순서

---

[플로이드-와샬]

일반적인 플로이드-와샬을 이용하여 모든 사람간의 키 순서를 구하면 된다. 여기까지는 유추하기 쉬울 수 있으나, 특정 사람 i가 몇 번째로 큰 것 인지에 대한 것을 판단하기는 약간 어려울 수 있다.

 

만일 특정 사람 i가 다른 사람 j에 대하여 키 관계를 모를 때, j 입장에서도 i의 키 관계를 모른다면 그것은 자신이 몇 번째로 큰 사람인지 모르는 것과 마찬가지이다.

 

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static final int INF = 1000000000;
    static int[][] d = new int[501][501];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i == j) continue;
                else d[i][j] = INF;

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            d[v2][v1] = 1;
        }

        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);

        int cnt = 0;
        for(int i=1; i<=n; i++) {
            boolean flag = true;

            for (int j = 1; j <= n; j++)
                if(d[i][j] == INF && d[j][i] == INF) {
                    flag = false;
                    break;
                }

            if(flag) cnt++;
        }

        System.out.println(cnt);
    }
}