207. Course Schedule

There are a total ofncourses you have to take, labeled from0ton - 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 prerequisitepairs, 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:

1. The input prerequisites is a graph represented by

   a list of edges, not adjacency matrices. Read more about how a graph is represented.

2. You may assume that there are no duplicate edges in the input prerequisites.

Hints:

1. 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.

2. Topological Sort via DFS

   • A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

3. Topological sort could also be done via BFS.

Thoughts: equivalent to cycle detection problem in topological sort (Kahn's algorithm vs DFS)

Code (Kahn's algorithm)

class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        // make graph outwards
        vector<unordered_set<int>> g(numCourses);
        vector<int> ind (numCourses, 0);

        for(auto p : prerequisites){
            g[p.second].insert(p.first);
        }
        // record in-degrees for each node
        for(auto p: prerequisites){
            ind[p.first]++;
        }

        for(int i = 0 ; i < numCourses; i++){
            int j = 0;
            for(; j < numCourses; j++){
                if(!ind[j]) break;
            }
            if(j== numCourses) return false;
            ind[j]--;
            for(int neigh: g[j]){
                ind[neigh]--;
            }
        }

        return true;
    }

};

Code (DFS)

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
        vector<bool> onpath(numCourses, false), visited(numCourses, false);
        for (int i = 0; i < numCourses; i++)
            if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
                return false;
        return true;
    }
private:
    vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph(numCourses);
        for (auto pre : prerequisites)
            graph[pre.second].insert(pre.first);
        return graph;
    } 
    bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
        onpath[node] = visited[node] = true; 
        for (int neigh : graph[node])
            // current node and its child nodes
            if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
                return true;
        // no neightbor case: leaf node, reset the onpath value so that this node can be re-visit 
        return onpath[node] = false;
    }
};

Special Thanks to jianchaolifighter's solution for referenece