#2360

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Longest Cycle in a Graph

The problem asks to find the longest cycle in a directed graph with specific edge constraints.

depth first search breadth first search graph topological sort

Problem Statement

You are given a directed graph with n nodes labeled 0 to n - 1, where each node has at most one outgoing edge. The graph is represented by an array of edges of length n, where edges[i] indicates the node to which node i points. If node i has no outgoing edge, edges[i] == -1.

Your task is to return the length of the longest cycle in the graph. If no cycle exists, return -1. A cycle is a path that starts and ends at the same node without repetition of any other nodes in between.

Examples

Example 1

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

Output: 3

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

There are no cycles in this graph.

Constraints

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

Solution Approach

Graph Indegree and Topological Ordering

This approach focuses on identifying nodes with an indegree of 0 and progressively processing them in topological order. This helps detect cycles by tracing back nodes that point to already-visited nodes, indicating a cycle.

Depth-First Search (DFS)

DFS is used to traverse through the graph, marking nodes as visited and backtracking when encountering a cycle. By tracking the nodes' visitation states, the longest cycle can be identified.

Breadth-First Search (BFS)

BFS can be used as an alternative to DFS by exploring the graph level by level. This is useful for identifying cycles in broader search spaces, providing a methodical check for longer cycles.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the traversal algorithm used. For DFS or BFS, it is O(n), where n is the number of nodes. Space complexity depends on the space used for marking visited nodes and storing cycle data, which is also O(n).

What Interviewers Usually Probe

Candidate's understanding of graph traversal techniques like DFS or BFS and their ability to detect cycles.
How well the candidate can optimize space and time complexity while dealing with graph traversal.
Ability to connect the graph indegree and topological ordering patterns to detect cycles efficiently.

Common Pitfalls or Variants

Common pitfalls

Confusing cycle detection with simple path finding.
Overlooking the need for revisiting nodes that are part of a potential cycle.
Incorrectly handling the case where no cycle exists and returning invalid results.

Follow-up variants

Graphs with multiple cycles or no cycles.
Graphs where some nodes point to themselves.
Optimizing for graphs with extremely large sizes, requiring efficient traversal.

FAQ

What is the key pattern for solving the Longest Cycle in a Graph problem?

The key pattern involves using graph indegree and topological ordering to detect cycles in a directed graph.

How does Depth-First Search (DFS) work for this problem?

DFS works by visiting nodes and backtracking when a cycle is found, marking nodes as visited to avoid revisiting them.

What is the time complexity for solving this problem?

The time complexity is O(n), where n is the number of nodes in the graph, as each node is visited once during traversal.

Can this problem be solved using Breadth-First Search (BFS)?

Yes, BFS can also be used by exploring nodes level by level, checking for cycles as nodes are revisited.

What should I do if no cycle exists in the graph?

If no cycle is found, the answer should be -1, indicating the absence of a cycle.

terminal

Solution

Solution 1: Traverse Starting Points

We can traverse each node in the range $[0,..,n-1]$. If a node has not been visited, we start from this node and search for adjacent nodes until we encounter a cycle or a node that has already been visited. If we encounter a cycle, we update the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        vis = [False] * n
        ans = -1
        for i in range(n):
            if vis[i]:
                continue
            j = i
            cycle = []
            while j != -1 and not vis[j]:
                vis[j] = True
                cycle.append(j)
                j = edges[j]
            if j == -1:
                continue
            m = len(cycle)
            k = next((k for k in range(m) if cycle[k] == j), inf)
            ans = max(ans, m - k)
        return ans

Continue Practicing

#2328 number of increasing paths in a grid #2192 all ancestors of a node in a directed acyclic graph #1462 course schedule iv