210. Course Schedule II

Same as "Course Schedule I". The only difference is push the course into result.

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