백준 2458 키 순서

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

2458번: 키 순서

 

 

키를 비교한 결과가 주어졌을 때  자신의 키가 몇번째인지 알수있는 학생이 몇명인지 알아내자.

 

 

키를 비교한 결과를 그래프로 나타내면 다음과 같다.

자신이 몇번쨰인지 알기 위해서는 

1. 다른 점에서 자기를 방문할수 있다.

2. 자기가 다른 점을 방문 할수 있다.

가 모든 점에 대해 만족 되야한다.

 

위의 그림에서 4번은 2,6번을 방문 할수있고, 1 3 5는 4를 방문할수 있으므로 4번은 자신의 순서를 알 수 있다.

그러므로 모든 정점 사이의 거리를 구하면된다.

모든 정점 사이의 거리를 구하는데 가장 적합한 알고리즘은 플로이드-와샬 알고리즘이다. (시간 복잡도 O(V^3))

플로이드-와샬을 적용해서 정점 사이의 거리를 모두 구하고

각 점에 대해서 D[i][j] != INF || D[j][i] !=INF 가 모든 정점 에 대해서 만족하는지 구해보면 된다.

 

 

import java.util.*;
import java.io.*;

public class Main {
	static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}

			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList <int[]> edges = new ArrayList<int[]>();
		int D [][]  = new int[N+1][N+1];
		int INF =987654321;
		
		for(int j =0 ;j <=N;j++) {
			Arrays.fill(D[j], INF);
			D[j][j] = 0;
		}
		for(int i =0 ;i < M;i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			D[u][v] = 1;
		}
		int answer =0 ;
		
		for(int i = 0 ;i<M;i++) {
			
		}
		for(int k=1;k<=N;k++) {
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					if(D[i][k]+D[k][j]< D[i][j]) {
						D[i][j] = D[i][k] + D[k][j];
					}
				}
			}
		}
			
fr:		for(int i =1 ;i <=N;i++) {
			for(int j = 1;j<=N;j++) {
				if(D[i][j]==INF&&D[j][i]==INF) continue fr;
			}
			answer++;
		
		}	
		System.out.println(answer);
		
	

}
		

}