207.Course Schedule

Topological Sort

1- BFS

class Solution {
    //O(V+E)
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses];
        int[] indegree = new int[numCourses];
        //E Part
        for(int[] pre : prerequisites){
            int preCourse = pre[1];
            int readyCourse = pre[0];
            indegree[readyCourse]++;
            matrix[preCourse][readyCourse] = 1;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for(int i = 0 ; i < numCourses; i++){
            if(indegree[i] == 0)
                queue.add(i);
        }
        int count = 0;
        while(!queue.isEmpty()){
            int course = queue.poll();
            count++;
            for(int i = 0; i < numCourses; i++){
                if(matrix[course][i] != 0){
                    if(--indegree[i] == 0){
                        queue.add(i);
                    }
                }
            }
        }
        return count == numCourses;
    }
}

    // O(V + E)
    List<Integer>[] matrix = new List[numCourses];
    int[] indegree = new int[numCourses];

    // E part
    for (int[] pre : prerequisites) {
        int preCourse = pre[1];
        int readyCourse = pre[0];
        List<Integer> list = matrix[preCourse];
        if (list == null) {
            list = new LinkedList<>();   
            matrix[preCourse] = list;
        }
        list.add(readyCourse);
        indegree[readyCourse]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i=0; i<numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    int count = 0;
    // V part
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        count++;
        List<Integer> adjacent = matrix[vertex];
        if (adjacent == null) continue;
        for (int neighbor : adjacent) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0)
                queue.offer(neighbor);
        }
    }
    return count == numCourses;