Longest Cycle in a Graph

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;
    }
};

In the provided C++ code, the goal is to identify the longest cycle in a directed graph represented by a vector of integers, where each integer denotes a connection from the index node to the value node. The function uses a combination of Kahn's algorithm for topological sorting and a cycle detection approach to solve this problem.

• The connections array provides a direct mapping from a node to another node, with -1 indicating no connection.
• A seen vector tracks which nodes have been processed to avoid counting a node multiple times.
• A node_indegree vector is prepared to count the inward edges (indegree) for each node, which is crucial for Kahn's algorithm.

Here’s a breakdown of the steps followed in the code:

1. Initialize a boolean vector seen and an integer vector node_indegree to track visited nodes and the indegree of nodes respectively.
2. Traverse through the connections array to fill up the node_indegree for each node.
3. Use a queue to facilitate Kahn’s algorithm. Nodes with zero indegree are initially pushed into the queue, signifying they have no dependencies.
4. Process each node in the queue, removing its contribution to other nodes’ indegree by decrementing. If this leads a node’s indegree to zero, it's added to the queue.
5. After iterating through the graph with Kahn's algorithm, nodes that have not been seen are part of a cycle. For each such node, track its path until a repeated node is found, calculating the cycle's length.
6. Maintain a variable longest_cycle_length to store the maximum length found during these traversals.
7. Return the length of the longest cycle found.

This approach ensures that all nodes are considered, and cycles are efficiently detected and measured for length, providing an effective manner to identify the longest cycle within the graph.

class Solution {
    public int findLongestCycle(int[] nodes) {
        int size = nodes.length;
        boolean[] visited = new boolean[size];
        int[] nodeInDegree = new int[size];

        // Summing up incoming edges
        for (int edge : nodes) {
            if (edge != -1) {
                nodeInDegree[edge]++;
            }
        }

        // Applying Kahn's algorithm
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            if (nodeInDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            visited[currentNode] = true;
            int nextNode = nodes[currentNode];
            if (nextNode != -1) {
                nodeInDegree[nextNode]--;
                if (nodeInDegree[nextNode] == 0) {
                    queue.offer(nextNode);
                }
            }
        }

        int maxCycleLength = -1;
        for (int i = 0; i < size; i++) {
            if (!visited[i]) {
                int cycleLen = 1;
                visited[i] = true;
                for (int next = nodes[i]; next != i; next = nodes[next]) {
                    visited[next] = true;
                    cycleLen++;
                }
                maxCycleLength = Math.max(maxCycleLength, cycleLen);
            }
        }
        return maxCycleLength;
    }
}

The JAVA program provided is designed to find the longest cycle in a directed graph represented as an array, where each position in the array points to the next node in the graph. Here's the approach used:

• Initialization:

  • Store the number of nodes.
  • Create arrays to track visited nodes and the in-degree of each node.

• Calculate In-Degrees:

  • Iterate through each node in the graph to sum up incoming edges by updating the in-degree for each target node specified by the current node's edge.

• Apply Kahn's Algorithm:

  • Initialize a queue to process nodes with zero in-degree (indicating there's no incoming edge).
  • Continue to dequeue and check if the next node in the sequence has had its in-degree reduced to zero after removing the current edge, then enqueue this next node.

• Identify Cycles:

  • After processing with Kahn's algorithm, any node that hasn't been visited will be part of a cycle.
  • Traverse the graph starting from these unvisited nodes to measure the length of each cycle. Update the maximum cycle length found.

• Return Result:

  • After all possible cycles have been examined, return the length of the longest cycle found. If no cycles are detected, the function responds with -1.

This holistic approach combines in-degree calculation, Kahn's algorithm for topological sorting, and cycle detection through direct traversal to efficiently find the maximum cycle length in the given graph.