백준 1766번: 문제집 [위상정렬][우선순위큐][그래프]-Java

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

우선순위 큐와 위상정렬을 이용해서 푸는 문제

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		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());
		
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		int indegree[] = new int[N+1];
		ArrayList<Integer> list[] = new ArrayList[N+1];
		
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int front = Integer.parseInt(st.nextToken());
			int back = Integer.parseInt(st.nextToken());
			
			list[front].add(back);
			indegree[back]++;
		}
		
		for (int i = 1; i <= N; i++) {
			if(indegree[i]==0)
				pq.add(i);
		}
		StringBuilder sb = new StringBuilder();
		
		while(!pq.isEmpty()) {
			int num = pq.poll();
			sb.append(num+" ");
			
			for(int n : list[num]) {
				indegree[n]--;
				if(indegree[n]==0)
					pq.add(n);
			}
		}
		
		System.out.println(sb);

	}

}