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.

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.

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
          int[] indegree = new int[numCourses];
          Map<Integer, List<Integer>> map = new HashMap<>();

          for(int i=0; i < prerequisites.length; i++){
                int p = prerequisites[i][1];
                int q = prerequisites[i][0];
                if(map.containsKey(p)){
                    map.get(p).add(q);
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(q);
                    map.put(p, list);
                }

                indegree[q]++;

          }
          //each course in this queue has no dependency on other courses.
          Queue<Integer> queue = new LinkedList<>();

          for(int i=0; i<numCourses; i++){
              if(indegree[i] == 0) queue.offer(i);
          }
          int res = 0;
          while(!queue.isEmpty()){
              int c = queue.poll();
              res++;

              if(map.containsKey(c)){
                  List<Integer> dep = map.get(c);
                  for(int cc : dep){
                      indegree[cc]--;
                      if(indegree[cc] == 0) queue.offer(cc);
                  }
              }
          }

          return res == numCourses;
    }
}

DFS solution, you still need to build the map for the edges, but this time, used a visited[] array to represent if the course is finished or not. for each course:

• mark it as visited
• visits it all dependent courses, if you reach any course twice, then there is a cycle.
• mark it as not visited, visit next course.

it has three states: unvisited (=0), visited(=1), searching(=-1). The third states is to detect the existence of cycle, while the 2nd state indicate that the vertex is already checked and there is no cycle, there is no need to check this vertex again, since we already verify that there is no circle from this vertex.

//taken from web
class Solution {
public:
    bool dfs(int v, vector<int> &visit, vector<set<int> > &gr){
        /* if this line maps to BFS, it means that I already checked all not
         * coming into this nodes , there is no cycle, all the nodes depends
         *  on this node, their in degree decrease by 1. 
         *  
         *  in other cases, if a node whose dominate node visited later, 
         *  this node is already marked as 1, then the dominate node is 
         *  visited later, when this node is trying to visited dependent
         *  node, it found that the node is already marked as visited and 
         *  validated, which means this node will not result in cycle, then
         *  the dominate node will also return as validated and visted.
         *  example:
         *  1 -> 2,  3 -> 2, 4 -> 2
         *  1. visit 1 first, then its dependents, 3, then 3's dependents 2, all
         *  is marked 1 , as visited and validated
         *  2. skip 2, 3 cause they are already processed.
         *  3, visit 4, and its dependents 2, which is already marked as good.
        if (visit[v] == 1){return true;}
        visit[v] = -1;
        for (auto it = gr[v].begin(); it != gr[v].end(); it++){
            if (visit[*it] == -1 || ! dfs(*it, visit, gr)){
                return false;
            }
        }
        visit[v] = 1;
        return true;
    }

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int plen = prerequisites.size();
        vector<int> visit(numCourses,0);
        vector<set<int> > gr(numCourses);

        for (int i=0;i<plen;i++){
            gr[prerequisites[i].second].insert(prerequisites[i].first);
        }

        for (int i=0;i<numCourses;i++){
            if (!dfs(i, visit, gr)) return false;
        }
        return true;
    }
};