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;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/course-schedule/
    // Time: O(V + E)
    // Space: O(V + E)
    class Solution {
    public:
        bool canFinish(int n, vector<vector<int>>& E) {
            vector<vector<int>> G(n);
            vector<int> indegree(n);
            for (auto &e : E) {
                G[e[1]].push_back(e[0]);
                ++indegree[e[0]];
            }
            queue<int> q;
            for (int i = 0; i < n; ++i) {
                if (indegree[i] == 0) q.push(i);
            }
            while (q.size()) {
                int u = q.front();
                q.pop();
                --n;
                for (int v : G[u]) {
                    if (--indegree[v] == 0) q.push(v);
                }
            }
            return n == 0;
        }
    };
    
  • class Solution(object):
      def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
    
        def dfs(start, parent, visited, graph):
          visited[start] = 1
          for nbr in graph[start]:
            if visited[nbr] == 1:
              return False
            if dfs(nbr, start, visited, graph) == False:
              return False
          visited[start] = 2
          return True
    
        graph = [[] for _ in range(0, numCourses)]
        for pre in prerequisites:
          start, end = pre
          graph[start].append(end)
    
        visited = [0 for _ in range(0, numCourses)]
    
        for pre in prerequisites:
          start, end = pre
          if visited[start] == 0:
            if dfs(start, None, visited, graph) == False:
              return False
        return True
    
    

All Problems

All Solutions