Longest Cycle in a Graph

Problem Statement

In this challenge, you are presented with a directed graph consisting of n nodes, precisely numbered from 0 to n-1. Each node in this graph can have at most one outgoing edge. The structure of the graph is depicted using a 0-indexed array named edges, where the element at index i (edges[i]) represents a directed edge from node i to node edges[i]. If a particular node i does not point to any other node, it is represented as edges[i] == -1.

Your goal is to determine the length of the longest cycle within the graph. A cycle refers to a sequence of nodes starting and ending at the same node, effectively forming a loop. If the graph contains no cycles, the function should return -1.

Examples

Example 1

Input:

edges = [3,3,4,2,3]

Output:

3

Explanation:

The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2.
The length of this cycle is 3, so 3 is returned.

Example 2

Input:

edges = [2,-1,3,1]

Output:

-1

Explanation:

There are no cycles in this graph.

Constraints

• n == edges.length
• 2 <= n <= 105
• -1 <= edges[i] < n
• edges[i] != i

Approach and Intuition

To tackle the problem of finding the longest cycle in the directed graph, you can employ the following strategy:

1. Cycle detection: Use a graph traversal technique, specific to identifying cycles. Depth-first search (DFS) or breadth-first search (BFS) can be particularly useful here since each node points to at most one other node.

2. Tracking Visited Nodes: Maintain an array or set to keep a record of visited nodes to detect cycles. Each time a node is revisited, a cycle is confirmed.

3. Determining Cycle Length:

   • Start traversing from each unvisited node using DFS/BFS.
   • Use a pointer or a marker to track the start of a cycle once you encounter a node that has been visited during the current traversal (indicating the cycle's start).
   • Once a cycle is detected, count its length by continuing the traversal until the start node is reached again.

4. Handling Nodes Without Outgoing Edges: Nodes pointing to -1 do not contribute to any cycle and can be ignored or marked as visited right at the start.

5. Achieving the Maximum Cycle Length:

   • For each unvisited node, if a cycle is detected during its traversal, compare its length with the maximum length found so far and update if it's longer.

6. Efficiency Considerations: Given that the graph may be large (up to 10^5 nodes), it's important to ensure that the cycle detection is as efficient as possible, leveraging direct index access in arrays and avoiding redundant checks.

By systematically applying the above approach, you can effectively determine the length of the longest cycle in the given graph configuration, once verifying its presence. If no cycles are found after examining all potential starting nodes, then return -1 as stipulated by the problem's constraints.

Solutions

class Solution {
public:
    int findLongestCycle(vector<int>& connections) {
        int count_nodes = connections.size();
        vector<bool> seen(count_nodes);
        vector<int> node_indegree(count_nodes);
    
        // Calculating the indegree for each node
        for (int conn : connections) {
            if (conn != -1) {
                node_indegree[conn]++;
            }
        }
    
        // Initiate Kahn's algorithm
        queue<int> process_queue;
        for (int i = 0; i < count_nodes; i++) {
            if (node_indegree[i] == 0) {
                process_queue.push(i);
            }
        }
    
        while (!process_queue.empty()) {
            int current_node = process_queue.front();
            process_queue.pop();
    
            seen[current_node] = true;
            int next_node = connections[current_node];
            if (next_node != -1) {
                node_indegree[next_node]--;
                if (node_indegree[next_node] == 0) {
                    process_queue.push(next_node);
                }
            }
        }
    
        int longest_cycle_length = -1;
        for (int i = 0; i < count_nodes; i++) {
            if (!seen[i]) {
                int cycle_length = 1;
                int current = connections[i];
                seen[i] = true;
                while (current != i) {
                    seen[current] = true;
                    cycle_length++;
                    current = connections[current];
                }
                longest_cycle_length = max(longest_cycle_length, cycle_length);
            }
        }
    
        return longest_cycle_length;
    }
};