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