diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /longest_cycle_graph.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-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.cpp | 58 |
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)); -} |