leetcode

commit 964a7589e6372942cbce58677c41e186f200066b
parent f69eb636ed287d5f4711d64791591a283f8a67f8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 26 Mar 2023 12:21:06 +0200

Daily Problem

Diffstat:
A
Problems/2360.cpp
 | 
33
+++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/2360.cpp b/Problems/2360.cpp
@@ -0,0 +1,33 @@
+class Solution {
+public:
+  int longestCycle(vector<int> &edges) {
+    int n = edges.size(), res = -1;
+    vector<int> count(n, 0);
+    for (int edge : edges)
+      if (edge != -1) count[edge]++;
+
+    queue<int> q;
+    for (int i = 0; i < n; i++)
+      if (!count[i]) q.push(i);
+
+    while (!q.empty()) {
+      int root = q.front();
+      q.pop();
+      if (edges[root] == -1) continue;
+      if (--count[edges[root]] == 0) q.push(edges[root]);
+    }
+
+    for (int i = 0; i < n; i++) {
+      if (!count[i]) continue;
+      int k = i, num = 1;
+      while (edges[k] != i) {
+        count[k] = 0;
+        k = edges[k];
+        num++;
+      }
+      res = max(res, num);
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -482,6 +482,7 @@ for solving problems.
 |  2343  |   Medium   | [Query Kth Smallest Trimmed Number](Problems/2343.cpp)                                           |
 |  2348  |   Medium   | [Number of Zero-Filled Subarrays](Problems/2348.cpp)                                                 |
 |  2359  |   Medium   | [Find Closest Node to Given Two Nodes](Problems/2359.cpp)                                        |
+|  2360  |    Hard    | [Longest Cycle in a Graph](Problems/2360.cpp)                                                    |
 |  2368  |   Medium   | [Reachable Nodes With Restrictions](Problems/2368.cpp)                                           |
 |  2374  |   Medium   | [Node With Highest Edge Score](Problems/2374.cpp)                                                |
 |  2390  |   Medium   | [Removing Stars From a String](Problems/2390.cpp)                                                |