Longest Cycle in a Graph

Intuitiona cycle is detected by where the current walk first repeats

Because every node has at most one outgoing edge, starting from a node gives you one forced path: there are no branching choices. The path either reaches -1, reaches a node already settled by an earlier start, or returns to a node that is still on the current path. Only the third case creates a new cycle.

While following one path, assign its nodes distances 0, 1, 2, and so on from the starting node. If the walk reaches a node already on this same path, the cycle begins at that node's stored distance and ends at the current distance. The difference between those distances is exactly the number of edges in the cycle. Once the path is finished, every node on it can be marked permanently processed, because its outgoing route has already been completely explored.

Approach

1. 1Keep three states for every node: 0 means unseen, 1 means on the path currently being followed, and 2 means fully processed. Without the distinction between states 1 and 2, an edge into an older finished path would be mistaken for a cycle.
2. 2Start a walk from every unseen node, keeping cur as the current node and d as its distance from this walk's start. Starting only from unseen nodes avoids repeating work already settled by an earlier walk.
3. 3While cur is not -1 and still unseen, mark it as state 1, store dist[cur] = d, increase d, and follow edges[cur]. These assignments record the exact position of every node on the current path before the walk advances.
4. 4When the walk stops at a state-1 node, compute d - dist[cur] and maximize the answer. The repeated node marks the cycle's beginning, so subtracting its first distance removes the non-cyclic prefix.
5. 5When the walk stops at -1 or at a state-2 node, do not update the answer. Both endings leave the current path without a newly discovered cycle.
6. 6Walk again from the original start while nodes are state 1 and change them to state 2. This retires precisely the current path, so later starts can skip it without confusing it with an active cycle.
7. 7Return the largest measured length, leaving the initial answer as -1 when no walk ever returns to an active node.

Complexityeach node is retired once

Annotated solutionC++ · iterative path walk · complete judge-ready implementation

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<int> state(n, 0);
        vector<int> dist(n, 0);
        int ans = -1;

        for (int i = 0; i < n; ++i) {
            if (state[i] != 0) {
                continue;
            }

            int cur = i;
            int d = 0;

            while (cur != -1 && state[cur] == 0) {
                state[cur] = 1;
                dist[cur] = d++;
                cur = edges[cur];
            }

            if (cur != -1 && state[cur] == 1) {
                ans = max(ans, d - dist[cur]);
            }

            cur = i;
            while (cur != -1 && state[cur] == 1) {
                state[cur] = 2;
                cur = edges[cur];
            }
        }

        return ans;
    }
};

The two values that make the measurement work are d and dist. At the moment the walk reaches cur again, d is the distance just after the last newly visited node, while dist[cur] is where the cycle started. The cleanup loop is equally important: state 1 is temporary evidence for the current walk, so every such node must become state 2 before another starting node is considered.

The indegree-pruning alternativea different arrangement that identifies cycle nodes first

You can also remove every node that cannot belong to a cycle. Compute indegrees, place all zero-indegree nodes in a queue, and repeatedly remove them while decreasing the indegree of their only outgoing neighbor. Every removed node is outside a cycle. The nodes left afterward are exactly the disjoint cycles, so you can walk each remaining cycle and count its length.

#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<int> indegree(n, 0);
        queue<int> q;

        for (int node = 0; node < n; ++node) {
            if (edges[node] != -1) {
                ++indegree[edges[node]];
            }
        }

        for (int node = 0; node < n; ++node) {
            if (indegree[node] == 0) {
                q.push(node);
            }
        }

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            int next = edges[node];

            if (next != -1 && --indegree[next] == 0) {
                q.push(next);
            }
        }

        int answer = -1;
        vector<bool> seen(n, false);

        for (int node = 0; node < n; ++node) {
            if (indegree[node] == 0 || seen[node]) {
                continue;
            }

            int length = 0;
            int cur = node;
            do {
                seen[cur] = true;
                ++length;
                cur = edges[cur];
            } while (cur != node);

            answer = max(answer, length);
        }

        return answer;
    }
};

This is not asymptotically faster: it is O(n) time and O(n) extra space, like the path-state solution. It buys a clean separation between elimination and measurement, and it avoids storing distances. The state-and-distance walk is usually shorter when you want the cycle length at the exact moment it is detected; pruning is a reasonable alternative when the surviving-cycle viewpoint feels more natural.

Common mistakesthree lines that change what counts as a cycle