시간제한 : 2초, 난이도 : 골드 3, 백준 : 2252번

원리

• 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각 해야 함
• 답이 여러 개일 때 아무것이나 출력해도 된다는 전제가 있음 → 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Practice53 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		ArrayList<ArrayList<Integer>> A = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			A.add(new ArrayList<>());
		}
		
		int []indegree = new int[N + 1]; //진입 차수 배열
		for(int i = 0; i < M; i++) {
			int S = sc.nextInt();
			int E = sc.nextInt();
			A.get(S).add(E);
			indegree[E]++;
		}
		
		Queue<Integer> queue = new LinkedList<>();
		for(int i = 1; i <= N; i++) {
			if(indegree[i] == 0) {
				queue.offer(i);
			}
		}
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			System.out.print(now + " ");
			for(int next : A.get(now)) {
				indegree[next]--;
				if(indegree[next] == 0) {
					queue.offer(next);
				}
			}
		}		
		
		sc.close();
	}

}