topological sort
O(V+E) time O(V+E) space
dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
visited.resize(numCourses);
g.resize(numCourses);
for (const auto &p : prerequisites) {
g[p[1]].push_back(p[0]);
}
for (int i = 0; i < numCourses; ++i) {
if (visited[i] == 0 && !dfs(i)) return false;
}
return true;
}
bool dfs(int x) {
if (visited[x]) return visited[x] == 1;
visited[x] = -1;
for (int y : g[x]) {
if (!dfs(y)) return false;
}
visited[x] = 1;
return true;
}
vector<int> visited;
vector<vector<int>> g;
};
|