210. Course Schedule II

time: O(V+E), refer to https://www.educative.io/edpresso/what-is-topological-sort

space: O(n)

same as 207's solution, use topology sort , just when

if (indegree[p[0]] == 0) {

record the result

and at last check res'length == numCouses

return (k == numCourses) ? res : new int[0];

這個例子 , 照理說 indegree 都會是 1 => indegree: [1, 1], so res[] 不應該有計算過, 但是要注意到...

int res[] = new int[numCourses]; ⇒ [0, 0]

因為初始化, int 是基本型台, 所以整個陣列就會是 0, 所以如果 res size 是 2, 就會變成 [0, 0]

所以最後才要加上這行, 不然無法呈現 [] 的結果

return (k == numCourses) ? res : new int[0];

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int indegree[] = new int[numCourses];
        int res[] = new int[numCourses];
        
        for (int p[] : prerequisites) {
            indegree[p[0]]++;
        }
        
        int k = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
                res[k++] = i;
            }
        }
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            for (int p[] : prerequisites) {
                if (pre == p[1]) {
                    indegree[p[0]]--;
                    if (indegree[p[0]] == 0) {
                        queue.offer(p[0]);
                        res[k++] = p[0];
                    }
                }
            }
        }
        return (k == numCourses) ? res : new int[0];
    }
}

better one

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List graph[] = new ArrayList[numCourses];
        int indegree[] = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        
        for (int edge[] : prerequisites) {
            graph[edge[1]].add(edge[0]); //construct graph
            indegree[edge[0]]++;
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int numChoose = 0;
        int order[] = new int[numCourses];
        while (!queue.isEmpty()) {
            int nowPos = queue.poll();
            order[numChoose++] = nowPos;
            for (int i = 0; i < graph[nowPos].size(); i++) {
                int nextPos = (int)graph[nowPos].get(i);
                indegree[nextPos]--;
                if (indegree[nextPos] == 0) {
                    queue.offer(nextPos);
                }
            }
        }
        return numChoose == numCourses ? order : new int[]{};
    }
}

// [0, 1] => 1 -> 0

new version

time: O(V+E), refer to https://www.educative.io/edpresso/what-is-topological-sort

space: O(n)

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> graph[] = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int p[] : prerequisites) {
            graph[p[1]].add(p[0]); // start -> end
            indegree[p[0]]++;
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] order = new int[numCourses];
        int orderIdx = 0;
        while (!queue.isEmpty()) {
            int pos = queue.poll();
            order[orderIdx++] = pos;
            
            for (int next : graph[pos]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return orderIdx == numCourses ? order : new int[]{};
    }
}


/*
prerequisites = [[1,0]]

0 -> 1
*/