Solution: Longest Cycle in a Graph
Explore how to identify and calculate the longest cycle in a directed graph where each node has at most one outgoing edge. Understand an iterative traversal approach that uses step counters and visitation tracking to detect cycles and compute their lengths. This lesson helps you implement an O(n) time and space algorithm to solve graph cycle problems effectively.
We'll cover the following...
Statement
You are given a directed graph with n nodes, labeled from 0 to n - 1. Each node in the graph has at most one outgoing edge.
The graph is described using a 0-indexed integer array edges of length n, where:
edges[i]represents a directed edge from nodeito nodeedges[i].If node
ihas no outgoing edge,edges[i] == -1.
Your task is to find longest cycle length in the graph. If no cycle exists, return -1.
Note: A cycle is defined as a path that starts and ends at the same node, following the direction of the edges.
Constraints:
nedges.length...