Question

Formatted question description: https://leetcode.ca/all/207.html

 207	Course Schedule

 There are a total of n courses you have to take, labeled from 0 to n - 1.

 Some courses may have prerequisites, for example to take course 0 you have to first take course 1,
 which is expressed as a pair: [0,1]

 Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?


 For example:

 2, [[1,0]]
 There are a total of 2 courses to take. To take course 1 you should have finished course 0.
 So it is possible.

 2, [[1,0],[0,1]]
 There are a total of 2 courses to take. To take course 1 you should have finished course 0,
    and to take course 0 you should also have finished course 1. So it is impossible.

 Note:

 The input prerequisites is a graph represented by a list of edges, not adjacency matrices.
    Read more about how a graph is represented.
 You may assume that there are no duplicate edges in the input prerequisites.


 click to show more hints.

 Hints:

 This problem is equivalent to finding if a cycle exists in a directed graph.
    If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
 Topological Sort via DFS
    A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
 Topological sort could also be done via BFS.

 @tag-graph

Algorithm

Kahn’s Algorithms：

https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm

BFS based，

• start from with vertices with 0 incoming edge，insert them into list S，at the same time we remove all their outgoing edges，
• after that find new vertices with 0 incoming edges and go on.

Tarjan’s Algorithms：

https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm DFS based，

• loop through each node of the graph in an arbitrary order，
• initiating a depth-first search that terminates when it hits any node that has already been visited
• since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node).

Code

Java

public class Course_Schedule {

    public class Solution_bfs {
        public boolean canFinish(int numCourses, int[][] prerequisites) { // Kahn's Algorithm
            if(numCourses <= 0) {
                return false;
            }

            if(prerequisites == null || prerequisites.length == 0) {
                return true;
            }

            int[] inDegree = new int[numCourses];

            // 1. setup indgree count
            for(int[] edge : prerequisites) {
                inDegree[edge[0]]++;
            }

            Queue<Integer> queue = new LinkedList<>();

            // 2. start from node with no indgree, i.e. no prerquisites for this course
            for(int i = 0; i < inDegree.length; i++) {
                if(inDegree[i] == 0) {
                    queue.offer(i);
                }
            }

            List<Integer> result = new ArrayList<>();

            while(!queue.isEmpty()) {
                int currentCourse = queue.poll();
                result.add(currentCourse);

                for(int[] edge : prerequisites) {
                    if(edge[1] == currentCourse) { // if a course requires current course

                        if(--inDegree[edge[0]] == 0) // -1, since current course is taken, and fulfill course edge[0]
                            queue.offer(edge[0]);
                    }
                }
            }

            return result.size() == numCourses;
        }
    }

    public class Solution_dfs {
        public boolean canFinish(int numCourses, int[][] prerequisites) {

            if(prerequisites == null || prerequisites.length < 2) {
                return true;
            }

            // 0 for not visited，1 for globally visited，-1 for visisted AND on current path
            int[] isVisited = new int[numCourses];
            List<List<Integer>> graph = new ArrayList<>();

            // 1. build graph
            for (int i = 0; i < numCourses; i++) {
                graph.add(new ArrayList<>());
            }
            for (int[] each: prerequisites) {
                graph.get(each[1]).add(each[0]);
            }

            // 2. dfs
            for (int i = 0; i < numCourses; i++) {
                if (!dfs(i, isVisited, graph)) {
                    return false;
                }
            }

            return true;
        }

        private boolean dfs(int courseIndex, int[] isVisited, List<List<Integer>> graph) {
            if (isVisited[courseIndex] == 1) {
                return true;
            }
            if (isVisited[courseIndex] == -1) {
                return false; // cycle found
            }

            isVisited[courseIndex] = -1;
            for (Integer next: graph.get(courseIndex)) {
                if(!dfs(next, isVisited, graph)) {
                    return false;
                }
            }

            isVisited[courseIndex] = 1;
            return true;
        }
    }

}

All Problems

All Solutions