leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0210.cpp (706B)

      1 class Solution {
      2   public:
      3     vector<int> findOrder(int n, vector<vector<int>> &prerequisites) {
      4         vector<vector<int>> adj(n);
      5         vector<int> count(n, 0);
      6         vector<int> res;
      7         int num = 0;
      8 
      9         for (auto &p : prerequisites) {
     10             adj[p[1]].push_back(p[0]);
     11             count[p[0]]++;
     12         }
     13 
     14         queue<int> q;
     15         for (int i = 0; i < n; i++)
     16             if (!count[i]) q.push(i);
     17 
     18         while (!q.empty()) {
     19             int root = q.front();
     20             q.pop();
     21             res.push_back(root);
     22             n--;
     23             for (int c : adj[root])
     24                 if (!--count[c]) q.push(c);
     25         }
     26         return n == 0 ? res : vector<int>();
     27     }
     28 };