leetcode

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

3310.cpp (1262B)

      1 static const auto _ = [] {
      2     ios::sync_with_stdio(0);
      3     cin.tie(0);
      4     return 0;
      5 }();
      6 
      7 class Solution {
      8   public:
      9     vector<int> remainingMethods(int n, int k, const vector<vector<int>> &invocations) const {
     10         static bool seen[100001];
     11         vector<vector<int>> invoke(n);
     12 
     13         memset(seen, 0x00, sizeof(seen));
     14         for (const auto &in : invocations) {
     15             invoke[in[0]].push_back(in[1]);
     16         }
     17 
     18         queue<int> q;
     19         q.emplace(k);
     20         seen[k] = true;
     21         while (!q.empty()) {
     22             const int root = q.front();
     23             q.pop();
     24             for (const auto next : invoke[root]) {
     25                 if (seen[next]) continue;
     26                 seen[next] = true;
     27                 q.emplace(next);
     28             }
     29         }
     30 
     31         for (int i = 0; i < n; i++) {
     32             if (seen[i]) continue;
     33             for (const auto in : invoke[i]) {
     34                 if (seen[in]) {
     35                     vector<int> res(n);
     36                     iota(begin(res), end(res), 0);
     37                     return res;
     38                 }
     39             }
     40         }
     41 
     42         vector<int> res;
     43         for (int i = 0; i < n; i++) {
     44             if (seen[i]) continue;
     45             res.emplace_back(i);
     46         }
     47 
     48         return res;
     49     }
     50 };