There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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 prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: 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.
Constraints:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5
Related Topics:
Depth-first Search, Breadth-first Search, Graph, Topological Sort
Similar Questions:
- Course Schedule II (Medium)
- Course Schedule II (Medium)
- Course Schedule II (Medium)
- Course Schedule II (Medium)
// OJ: https://leetcode.com/problems/course-schedule/
// Author: github.com/lzl124631x
// Time: O(V + E)
// Space: O(V + E)
class Solution {
public:
bool canFinish(int N, vector<vector<int>>& E) {
vector<vector<int>> G(N);
vector<int> indegree(N);
for (auto &e : E) {
G[e[1]].push_back(e[0]);
++indegree[e[0]];
}
queue<int> q;
for (int i = 0; i < N; ++i) {
if (indegree[i] == 0) q.push(i);
}
int cnt = 0;
while (q.size()) {
int u = q.front();
q.pop();
++cnt;
for (int v : G[u]) {
if (--indegree[v] == 0) q.push(v);
}
}
return cnt == N;
}
};// OJ: https://leetcode.com/problems/course-schedule/
// Author: github.com/lzl124631x
// Time: O(V + E)
// Space: O(V + E)
class Solution {
vector<int> state; // -1 unvisited, 0 visiting, 1 visited
bool dfs(vector<vector<int>> &G, int u) {
if (state[u] != -1) return state[u];
state[u] = 0;
for (int v : G[u]) {
if (!dfs(G, v)) return false;
}
return state[u] = 1;
}
public:
bool canFinish(int N, vector<vector<int>>& E) {
vector<vector<int>> G(N);
state.assign(N, -1);
for (auto &e : E) G[e[1]].push_back(e[0]);
for (int i = 0; i < N; ++i) {
if (!dfs(G, i)) return false;
}
return true;
}
};