207. Course Schedule

You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

[a, b] => b first : b -> a

[1] first, [0] is node, so cal indegree in [0]

use topology sort

cal indegree, if indegree == 0 put into queue (means prerequs..), Then BFS

indegree 0 means it's a start point

for loop , look up which course first ([1]) need start point (means start from this

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // topology order
        int indegree[] = new int[numCourses];
        int res = numCourses;
        for (int pair[] : prerequisites) { // why indegree, find indegree == 0 start to finish, that's the solution
            indegree[pair[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i< indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i); // add indegree == 0 as start point
            }
        }
        
        // [4,3] => graph: 3-4. => indegree => 3: 0, 4: 1
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            res--;
            for (int pair[] : prerequisites) {
                if (pre == pair[1]) { // when pair[1](prerequisites) match the start point
                    indegree[pair[0]]--; // do -- 
                    if (indegree[pair[0]] == 0) { // pair[0]'s indegree == 0, means pair[0] can be a new start point
                        queue.offer(pair[0]); // add start point
                    }
                }
            }
        }
        return res == 0; // means we finish all courses
    }
}

new version

time: O(V+E)

space: O(n), n is numCourses

class Solution {
    public boolean canFinish(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]]++;
        }
        
        int res = numCourses;
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int pos = queue.poll();
            res--;
            for (int next : graph[pos]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return res == 0;
    }
}


/*
prerequisites = [[1,0]]

0 -> 1
*/