207. Course Schedule

A typical topology sort problem. The following youtube is a very good material explaining topology sort.
https://www.youtube.com/watch?v=XPM9Q2LMxFk&list=PLqD_OdMOd_6YixsHkd9f4sNdof4IhIima&index=11

In this problem, there are three points.
1. use adjacent-list to represent the graph. In c++, the representation can be vector<unordered_set<int>>.
2. To make a successful topology sort, we need to make sure there is no cycle in the graph. This can be done by DFS.
3. We need two vectors to keep track of visited vertex. The visited vector keeps global graph vertex status. The path vector keeps the vertex status in one dfs function, i.e. vertices connected directly or remotely with one particular vertex.

1:  class Solution {  
2:  public:  
3:    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {  
4:      vector<unordered_set<int>> graph(numCourses);  
5:      construct_graph(graph, prerequisites);  
6:      vector<bool> visited(numCourses, false);  
7:      vector<bool> path(numCourses, false);  
8:      for (int i = 0; i < numCourses; i++) {  
9:        if (!visited[i] && dfs(graph, i, path, visited))  
10:          return false;  
11:      }  
12:      return true;  
13:    }  
14:    void construct_graph(vector<unordered_set<int>> &graph, vector<pair<int, int>> &prerequisites) {  
15:      for (int i = 0; i < prerequisites.size(); i++) {  
16:        graph[prerequisites[i].first].insert(prerequisites[i].second);  
17:      }  
18:    }  
19:    bool dfs(vector<unordered_set<int>> &graph, int vertex, vector<bool> &path, vector<bool> &visited) {  
20:      if (visited[vertex]) return false;  
21:      path[vertex] = visited[vertex] = true;  
22:      for (auto v: graph[vertex]) {  
23:        if (path[v] || dfs(graph, v, path, visited)) {  
24:          return true;  
25:        }  
26:      }  
27:      path[vertex] = false;  
28:      return false;  
29:    }  
30:  };   

Note line 21 and line 27, we revert the path[vertex] status to false in the end because path is a reference and we don't find any cycle. The reason we don't have to worry about if dfs() changes the path[v] to false is once we find a cycle we return true all the way up to the top of stack and we don't have to worry about the path again. On the other hand, if no cycle is found, each dfs() will revert the path[vertex] status.