2360. Longest Cycle

Longest Cycle in a Graph

A classic cycle detection problem — DFS is the most intuitive way.

One advantage of this problem is that these $n$ nodes are labeled $0$ to $n - 1$ as non-negative integers, so a plain vector<int> works perfectly to track visit orders.

Using unordered_map<int, int> would be much slower......🐢

When Does a Cycle Form? Think About It First

As we recursively traverse this directed graph and arrive at node $u$,

if $u$ has no outgoing edge, it's a dead end — node $u$ is no part of any cycle.

Now suppose $u$ has an outgoing edge toward node $v$. Node $v$ has three possible states:

I. Not yet visited 🔴

II. Currently on the recursion stack 🟡

III. Previously visited and already off the stack 🟢

Which state marks the moment a cycle is formed?

The answer is state II — currently on the recursion stack 🟡 That's the moment to celebrate a newly formed cycle 🎊

$(u, v)$ is the last piece of puzzle for this new cycle $C$ 🧩

Node $v$ is this cycle's start and node $u$ is the end 🏁. Length of cycle $C$ is $d[u] + 1 - d[v]$,

where $d[u]$ and $d[v]$ are the visit orders of nodes $u$ and $v$ respectively.

Since we are asked to find the longest cycle, whenever a new cycle forms,

we compare $d[u] + 1 - d[v]$ against the current best and update if it's a new record.

A Handy Tracking Trick

One small detail worth noting: to quickly distinguish between states II and III above,

I like to use different markers in the integer array visitedOrders:

1. -1: node not yet visited 🔴
2. Positive integer: node is on recursion stack 🟡. Integer is node's visit order
3. -2: node has been visited and popped off stack 🟢

Each node and each edge is visited exactly once. Time complexity is $O(V + E)$.

Space complexity is also $O(V + E)$.

C++

#include <vector>
using namespace std;

class LongestCycle // LeetCode Q.2360.
{
private:
    vector<int> graph, visitedOrders;
    int currentOrder = 1, maxCycle = -1;

    void dfsCycle(int node) {
        visitedOrders[node] = currentOrder;
        currentOrder++; // Increment for the next node.

        int tgtNode = graph[node];
        if (tgtNode == -1) // No outgoing edge.
        {
            visitedOrders[node] = -2; // Current node finalizes DFS.
            return;
        }

        if (visitedOrders[tgtNode] == -1) // Unvisited yet.
            dfsCycle(tgtNode);

        int tgtNodeOrder = visitedOrders[tgtNode];

        // Target node is also still under DFS: a cycle just forms.
        if (tgtNodeOrder > 0) {
            // Such a cycle starts at target, and ends at current node.
            int cycleLen = visitedOrders[node] + 1 - tgtNodeOrder;
            if (cycleLen > maxCycle)
                maxCycle = cycleLen;
        }

        visitedOrders[node] = -2; // Current node finalizes DFS.
    }

public:
    int computeLongestCycle(vector<int>& edges) {
        graph = edges;

        // Special marks: -1 = unvisited. -2 = has finalized DFS.
        visitedOrders.assign(edges.size(), -1);

        for (int node = 0; node < edges.size(); node++) {
            if (visitedOrders[node] == -1) // Unvisited yet.
                dfsCycle(node);
        }

        return maxCycle;
    }
};

Python

class LongestCycle:  # LeetCode Q.2360.
    def __init__(self):
        self.edges: list[int] = []
        self.visited_orders: list[int] = []

        self.current_order = 1
        self.longest_cycle = -1

    def _dfs_cycle(self, node: int) -> None:
        self.visited_orders[node] = self.current_order
        self.current_order += 1  # Increment for the next node.

        tgt_node = self.edges[node]
        if tgt_node == -1:  # No outgoing edge.
            self.visited_orders[node] = -2  # Current node finalizes DFS.
            return

        if self.visited_orders[tgt_node] == -1:  # Unvisited yet.
            self._dfs_cycle(tgt_node)

        tgt_node_order = self.visited_orders[tgt_node]

        # Target node still under DFS: a cycle just forms.
        if tgt_node_order > 0:
            # Such a cycle starts at target, and ends at current node.
            cycle_len = self.visited_orders[node] + 1 - tgt_node_order
            if cycle_len > self.longest_cycle:
                self.longest_cycle = cycle_len

        self.visited_orders[node] = -2  # Current node finalizes DFS.

    def compute_longest_cycle_len(self, edges: list[int]) -> int:
        self.edges = edges

        # Special marks: -1 = unvisited yet. -2 = has finalized DFS.
        self.visited_orders = [-1] * len(edges)

        self.current_order = 1
        self.longest_cycle = -1

        for node, _ in enumerate(edges):
            if self.visited_orders[node] == -1:  # Unvisited yet.
                self._dfs_cycle(node)

        return self.longest_cycle

Follow-up Problem

If problem 2360 is clear, come take this.