[LeetCode] Course Schedule

As suggested by the hints, this problem is equivalent to detecting a cycle in the graph represented by prerequisites. Both BFS and DFS can be used to solve it using the idea oftopological sort. If you find yourself unfamiliar with these concepts, you may refer to their wikipedia pages. Specifically, you may only need to refer to the link in the third hint to solve this problem.

Since pair<int, int> is inconvenient for the implementation of graph algorithms, we first transform it to a graph. If course u is a prerequisite of course v, we will add a directed edge from node u to node v.

BFS

BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we have found one. We set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of all its neighbors by 1. This process will be repeated for n (number of nodes) times. If we have not returned false, we will return true.

 1 class Solution {
 2 public:
 3     bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
 4         vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
 5         vector<int> degrees = compute_indegree(graph);
 6         for (int i = 0; i < numCourses; i++) {
 7             int j = 0;
 8             for (; j < numCourses; j++)
 9                 if (!degrees[j]) break;
10             if (j == numCourses) return false;
11             degrees[j] = -1;
12             for (int neigh : graph[j])
13                 degrees[neigh]--;
14         }
15         return true;
16     }
17 private:
18     vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
19         vector<unordered_set<int>> graph(numCourses);
20         for (auto pre : prerequisites)
21             graph[pre.second].insert(pre.first);
22         return graph;
23     }
24     vector<int> compute_indegree(vector<unordered_set<int>>& graph) {
25         vector<int> degrees(graph.size(), 0);
26         for (auto neighbors : graph)
27             for (int neigh : neighbors)
28                 degrees[neigh]++;
29         return degrees;
30     }
31 };

DFS

For DFS, it will first visit a node, then one neighbor of it, then one neighbor of this neighbor... and so on. If it meets a node which was visited in the current process of DFS visit, a cycle is detected and we will return false. Otherwise it will start from another unvisited node and repeat this process till all the nodes have been visited. Note that you should make two records: one is to record all the visited nodes and the other is to record the visited nodes in the current DFS visit.

The code is as follows. We use a vector<bool> visited to record all the visited nodes and another vector<bool> onpath to record the visited nodes of the current DFS visit. Once the current visit is finished, we reset the onpath value of the starting node to false.

 1 class Solution {
 2 public:
 3     bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
 4         vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
 5         vector<bool> onpath(numCourses, false), visited(numCourses, false);
 6         for (int i = 0; i < numCourses; i++)
 7             if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
 8                 return false;
 9         return true;
10     }
11 private:
12     vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
13         vector<unordered_set<int>> graph(numCourses);
14         for (auto pre : prerequisites)
15             graph[pre.second].insert(pre.first);
16         return graph;
17     } 
18     bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
19         if (visited[node]) return false;
20         onpath[node] = visited[node] = true; 
21         for (int neigh : graph[node])
22             if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
23                 return true;
24         return onpath[node] = false;
25     }
26 };