leetcode

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

2360.cpp (832B)

      1 class Solution {
      2   public:
      3     int longestCycle(vector<int> &edges) {
      4         int n = edges.size(), res = -1;
      5         vector<int> count(n, 0);
      6         for (int edge : edges)
      7             if (edge != -1) count[edge]++;
      8 
      9         queue<int> q;
     10         for (int i = 0; i < n; i++)
     11             if (!count[i]) q.push(i);
     12 
     13         while (!q.empty()) {
     14             int root = q.front();
     15             q.pop();
     16             if (edges[root] == -1) continue;
     17             if (--count[edges[root]] == 0) q.push(edges[root]);
     18         }
     19 
     20         for (int i = 0; i < n; i++) {
     21             if (!count[i]) continue;
     22             int k = i, num = 1;
     23             while (edges[k] != i) {
     24                 count[k] = 0;
     25                 k = edges[k];
     26                 num++;
     27             }
     28             res = max(res, num);
     29         }
     30 
     31         return res;
     32     }
     33 };