leetcodeSolution to some Leetcode problems written in C++ |
git clone git://git.dimitrijedobrota.com/leetcode.git |
Log | Files | Refs | README | LICENSE |
0207.cpp (678B)
0 class Solution {
1 static int adj[2048][2048];
3 public:
4 bool canFinish(int n, const vector<vector<int>> &prerequisites) {
5 int count[2048] = {0}, size[2048] = {0};
7 for (auto &p : prerequisites) {
8 adj[p[0]][size[p[0]]++] = p[1];
9 count[p[1]]++;
10 }
12 queue<int> q;
13 for (int i = 0; i < n; i++)
14 if (!count[i]) q.push(i);
16 while (!q.empty()) {
17 int root = q.front();
18 q.pop(), n--;
19 for (int i = 0; i < size[root]; i++)
20 if (!--count[adj[root][i]]) q.push(adj[root][i]);
21 }
23 return n == 0;
24 }
25 };
27 int Solution::adj[2048][2048];