https://www.acmicpc.net/problem/1766
기본적인 위상정렬문제로 해결
1. graph
라는 List배열을 할당해주고,
2. 각각 인덱스에 후속작업의 인덱스를 넣어줌. graph[pre].add(post)
넣어주면서, 전 작업이 필요한 경우 count를 올려줌. inDegree[post]++
4번은 1번 앞에 있어야함 =>
graph(1).add(4)
,
5번은 1번 앞에있어야함 =>graph(1).add(5)
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer>[] graph;
static int[] inDegree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
graph = new ArrayList[N+1];
inDegree = new int[N+1];
for(int i = 1; i < N+1; i++) {
graph[i] = new ArrayList<Integer>();
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int pre = Integer.parseInt(st.nextToken());
int post = Integer.parseInt(st.nextToken());
graph[pre].add(post);
inDegree[post]++;
}
topologicalSort();
}
static void topologicalSort() {
PriorityQueue<Integer> q = new PriorityQueue<Integer>();
for(int i = 1; i < N+1; i++) {
if(inDegree[i] == 0) q.offer(i);
}
while(!q.isEmpty()) {
int cur = q.poll();
System.out.println(cur);
for(int i = 0; i < graph[cur].size(); i++) {
int link = graph[cur].get(i);
inDegree[link]--;
if(inDegree[link] == 0) q.offer(link);
}
}
}
}