위상정렬

비순환 방향 그래프의 정점을 정렬
사이클이 존재하면 위상정렬이 불가

응용

선수 과정, 컴파일 작업 순서 등

시간복잡도

V : 정점, E : 간선

• 인접리스트 : $O(V+E)$
• 인접행렬 : $O(V^2)$

1. 그래프 연결
2. 각 노드로 들어오는 간선 수(indegree) 체크
3. indegree가 0인 노드부터 Queue에 넣는다
4. 인접 노드를 Queue에 넣고 indegree--
5. Queue가 빌때까지 3,4 반복

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

public class Main {

	public static void main(String[] args) throws IOException{

		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());
		
		int[] indegree = new int[n+1];
		ArrayList<Integer>[] list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		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] += 1;
			
		}
		
		topologySort(list, indegree, n);
		
		
	}
	
	static void topologySort(ArrayList<Integer>[] list, int[] indegree, int n) {
		Queue<Integer> q = new LinkedList<>();
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<indegree.length; i++) {
			if(indegree[i] == 0) {
				q.add(i);
			}
		}
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			sb.append(cur+" ");	
			
			for(int next : list[cur]) {
				indegree[next]--;
				if(indegree[next] == 0) {
					q.add(next);
				}
			}
		}
		
		System.out.println(sb);
		
	}

}