위상 정렬

위상 정렬

• 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
• 시간 복잡도 : O(V+E)
• 가장 먼저 진입 차수 값을 계산하고 진입 차수 배열을 만든다.
• 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택한 노드를 정렬 배열에 추가한다.
• 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺀다

백준2252

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();

        ArrayList<ArrayList<Integer>> A = new ArrayList<>();
        for(int i=0; i<=n; i++){
            A.add(new ArrayList<>());
        }

        int[] arr = new int[n+1];
        for(int i=0; i<m; i++){
            int a = input.nextInt();
            int b = input.nextInt();
            A.get(a).add(b);
            arr[b]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i=1; i<=n; i++){
            if(arr[i] == 0){
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()){
            int now = queue.poll();
            System.out.print(now + " ");
            for(int next : A.get(now)){
                arr[next]--;
                if(arr[next] == 0){
                    queue.offer(next);
                }
            }
        }
    }
}