문제 이해

N명의 학생을 키 순서대로 줄을 세우려 한다.
모든 학생의 정확한 키는 주어지지 않고, 단지 (A,B) 쌍이 주어진다.
(A,B)는 A의 키가 B보다 작다는 것이다.

이 경우 키 순서대로 줄을 세운 결과를 출력하는 문제이다(답이 여러 개일 경우 아무거나 출력)

---

문제 풀이

먼저 Edge의 수가 정확히 정해지지 않기 때문에 이 그래프가 Tree인지, 몇 개의 연결 요소로 되어 있는지도 알 수가 없다.

하지만 "키"라는 특성으로 알 수 있는 것이 있다.

바로 사이클이 일어나지 않는 그래프를 만들 것이며, 크기가 존재하는 방향 그래프라는 것이다.
즉, DAG라는 것을 의미하며, 위상 정렬을 통해 문제를 해결할 수 있을 것이라고 생각하였다.

위상정렬 알고리즘의 구현 방법은 여러 개 존재하겠지만, 그래프에서 Input Edge가 없는 Node들을 뽑아내는 방법을 통해 문제를 해결하겠다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static ArrayList<Integer>[] lists;
	static int[] input;
	
	static void sort() {
		Queue<Integer> queue = new LinkedList<>();
		for(int i =1;i<N+1;i++) {
            // input = 0인 Node들 뽑아냄
			if(input[i]==0) queue.add(i);
		}
		
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			sb.append(tmp+" ");
  
			for(int s:lists[tmp]) {
				input[s]--; 
                // tmp -> X인 Edge가 존재할 때, tmp Node를 삭제할 것이므로 
                // X의 input값 또한 1 감소 시킨다.
				if(input[s]==0) queue.add(s);
                // input[s] = 0이라면 위상 정렬 후보에 들어가야하므로, 
                // queue에 추가시켜준다.
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		lists = new ArrayList[N+1];
		input = new int[N+1];
		
		for(int i =1;i<N+1;i++) {
			lists[i] = new ArrayList<>();
		}
		
		for(int i=0;i<M;i++) {
			int tmp1= sc.nextInt();
			int tmp2 = sc.nextInt();
			
			lists[tmp1].add(tmp2);
            // tmp1의 키가 tmp2 보다 작음. 순서 : tmp1 -> tmp2
			input[tmp2]++; 
            // tmp2쪽으로 들어가는 Edge이므로 input 값을 1 증가 시켜준다
		}
		
		sort();
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과