aboutsummaryrefslogtreecommitdiff
path: root/longest_cycle_graph.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /longest_cycle_graph.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'longest_cycle_graph.cpp')
-rw-r--r--longest_cycle_graph.cpp58
1 files changed, 0 insertions, 58 deletions
diff --git a/longest_cycle_graph.cpp b/longest_cycle_graph.cpp
deleted file mode 100644
index b0cdf49..0000000
--- a/longest_cycle_graph.cpp
+++ /dev/null
@@ -1,58 +0,0 @@
-// 2360. Longest Cycle in a Graph
-#include "leetcode.h"
-
-/*
- * given a directed graph of 'n' nodes numbered from 0 to n - 1, where each node
- * has at most one outgoing edge. the graph is represented with a given
- * 0-indexed array 'edges' of size n, indicating that there is a directed edge
- * from node i to node edges[i]. if there is no outgoing edge from node i, then
- * edges[i] == -1. return length of longest cycle in the graph. if no cycle
- * exists, return -1. a cycle path starts at same node.
- */
-
-class Solution {
-public:
- int longestCycle(vector<int> &edges) {
- vector<bool> vis(edges.size(), 0);
- for (int i = 0; i < edges.size(); i++) {
- if (vis[i])
- continue;
- vector<int> store;
- dfs(edges, i, vis, store);
- }
- return max_len;
- }
-
-private:
- int max_len = -1;
- void dfs(vector<int> &edges, int si, vector<bool> &vis, vector<int> &store) {
- if (si == -1)
- return;
- if (vis[si]) {
- int cnt = -1;
- for (int i = 0; i < store.size(); i++) {
- if (store[i] == si) {
- cnt = i;
- break;
- }
- }
- if (cnt == -1)
- return;
- int size = store.size() - cnt;
- max_len = max(max_len, size);
- return;
- }
- vis[si] = true;
- store.push_back(si);
- dfs(edges, edges[si], vis, store);
- return;
- }
-};
-
-int main() {
- Solution obj;
- vector<int> e1 = {3, 3, 4, 2, 3};
- vector<int> e2 = {2, -1, 3, 1};
- printf("%d\n", obj.longestCycle(e1));
- printf("%d\n", obj.longestCycle(e2));
-}