package LeetCode;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;

public class LC_210 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
    }

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        Deque<Integer> que = new ArrayDeque<>();
        int[] indeg = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] rela : prerequisites) {
            list.get(rela[1]).add(rela[0]);
            indeg[rela[0]]++;
        }
        for (int i = 0; i < indeg.length; i++) {
            if (indeg[i] == 0) que.add(i);
        }
        while (!que.isEmpty()) {
            int u = que.pop();
            res.add(u);
            for (Integer v : list.get(u)) {
                indeg[v]--;
                if (indeg[v] == 0) que.add(v);
            }
        }
        if (res.size() == numCourses) return res.stream().mapToInt(Integer::intValue).toArray();
        return new int[]{};
    }
}