문제 풀이

물건 간의 대소관계를 그래프로 만들면 간단하다.

1번 물건을 2번 물건과 비교할 수 있는지 판단하려면 그래프로 대소관계를 그래프로 만들어 1에서 2, 또는 2에서 1로 갈 수 있는지 확인하면된다.

그렇게 하기 위해서는 플로이드 와샬 알고리즘을 사용한다.
플로이드 와샬알고리즘은 정점a에서 정점b까지의 최단거리를 구할 수 있다.

이 문제에서는 거리는 필요없고 갈 수 있는지만 확인하면 되기 때문에 가중치는 1로 둬도 무방하다.

플로이드 와샬알고리즘으로 최단거리를 구하고 처음 초기화한 987654321이 그대로 남아있다면 갈 수 없는것으로 판단한다.
양방향 모두 갈 수 없다면 비교할 수 없는 것으로 판단하면된다.

문제 링크

boj/10159

소스코드

PS/10159.java

import java.io.*;

import java.sql.Array;
import java.util.*;


public class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] map;
    static int[] grow_weight;
    static int[][] grow;

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int [][]d = new int [n+1][n+1];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=j)
                    d[i][j] = 987654321;
            }
        }
        for(int i=0;i<m;i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a =Integer.parseInt(st.nextToken());
            int b =Integer.parseInt(st.nextToken());
            d[a][b] =1;
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    if(d[j][k] > d[j][i] +d[i][k])
                        d[j][k] = d[j][i]+d[i][k];
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            int cnt = 0;
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    continue;
                cnt += d[i][j] == 987654321 && d[j][i] == 987654321 ? 1:0;
            }
            System.out.println(cnt);
        }
    }

}