Quick Overview

A coding question that asks whether a directed graph, given as a node count and a list of edges, contains at least one directed cycle. It tests graph traversal on large inputs and careful handling of self-loops, duplicate edges, converging paths and disconnected components.

Detect whether a directed graph given as an edge list contains a cycle

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a directed graph with `n` nodes labeled `0` to `n - 1` and a list of directed edges. Return whether the graph contains at least one directed cycle. ### Function Signature ```python def has_cycle(n: int, edges: list[list[int]]) -> bool: ``` `edges[i] = [u, v]` is a directed edge from node `u` to node `v`. ### Rules - A directed cycle is a path of one or more edges that follows edge directions and returns to the node it started from. - A self-loop `[u, u]` is a cycle of length one. - The same edge may appear more than once. Two copies of the edge from `u` to `v` do not form a cycle by themselves. - The graph may be disconnected, and some nodes may have no edges at all. - Return `True` if at least one directed cycle exists anywhere in the graph, otherwise `False`. ### Constraints - `1 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5` - `0 <= u <= n - 1` and `0 <= v <= n - 1` for every edge `[u, v]` ### Examples **Example 1** ```text Input: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]] Output: False ``` Node 3 can be reached from node 0 along two paths, `0 -> 1 -> 3` and `0 -> 2 -> 3`, but no path ever leads back to a node it has already passed through. **Example 2** ```text Input: n = 5, edges = [[4, 0], [0, 1], [1, 2], [2, 3], [3, 1]] Output: True ``` The edges `1 -> 2`, `2 -> 3` and `3 -> 1` form a cycle. **Example 3** ```text Input: n = 2, edges = [[0, 1], [1, 1]] Output: True ``` The self-loop on node 1 is a cycle of length one.

Overview: A coding question that asks whether a directed graph, given as a node count and a list of edges, contains at least one directed cycle. It tests graph traversal on large inputs and careful handling of self-loops, duplicate edges, converging paths and disconnected components.

Read the full Oracle Software Engineer interview experience this question came from

You are given a directed graph with `n` nodes labeled `0` to `n - 1` and a list `edges`, where `edges[i] = [u, v]` is a directed edge from node `u` to node `v`. Return whether the graph contains at least one directed cycle. ### Rules - A directed cycle is a path of one or more edges that follows edge directions and returns to the node it started from. - A self-loop `[u, u]` is a cycle of length one. - The same edge may appear more than once. Two copies of the edge from `u` to `v` do not form a cycle by themselves. - The graph may be disconnected, and some nodes may have no edges at all. - Return `True` if at least one directed cycle exists anywhere in the graph, otherwise `False` (`true` / `false` in JavaScript, Java and C++). ### Constraints - `1 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5` - Every `edges[i]` is a pair `[u, v]` with `0 <= u <= n - 1` and `0 <= v <= n - 1` - All values fit in a 32-bit signed integer; no value exceeds `2^31 - 1`. ### Example 1 ```text Input: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]] Output: False ``` Node 3 can be reached from node 0 along two paths, `0 -> 1 -> 3` and `0 -> 2 -> 3`, but no path ever leads back to a node it has already passed through. ### Example 2 ```text Input: n = 5, edges = [[4, 0], [0, 1], [1, 2], [2, 3], [3, 1]] Output: True ``` The edges `1 -> 2`, `2 -> 3` and `3 -> 1` form a cycle.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • edges[i] = [u, v] with 0 <= u <= n - 1 and 0 <= v <= n - 1
  • Self-loops and repeated identical edges may appear; the graph may be disconnected and nodes may have no edges
  • All values fit in a 32-bit signed integer (none exceeds 2^31 - 1)

Examples

Input: (4, [[0, 1], [0, 2], [1, 3], [2, 3]])

Expected Output: False

Explanation: Source Example 1: diamond DAG; node 3 is reached along two paths but no path returns to its start.

Input: (5, [[4, 0], [0, 1], [1, 2], [2, 3], [3, 1]])

Expected Output: True

Explanation: Source Example 2: edges 1 -> 2, 2 -> 3, 3 -> 1 form a cycle reached from the source chain 4 -> 0 -> 1.

Hints

  1. Reaching the same node along two different paths, like node 3 in Example 1, is not a cycle. A cycle needs a path that comes back to the node where it started.
  2. The graph may be disconnected, so a cycle can sit in a part of the graph that node 0 cannot reach. Make sure every node is considered.
  3. A self-loop [u, u] counts as a cycle, but repeated copies of the same edge u -> v do not. Your handling of edges must keep these two cases apart.

Loading coding console...

Show the approach

Approach

Algorithm (Kahn-style peeling): count every node's in-degree, counting each copy of a repeated edge, and build adjacency lists. Put every node with in-degree 0 into a work list, then repeatedly take the next node from the list, decrement the in-degree of each out-neighbor once per edge copy, and append any neighbor whose in-degree drops to 0. The graph has a cycle exactly when fewer than n nodes are ever taken.

Invariant: a node is taken only when every one of its incoming edges comes from a node that was taken earlier.

Correctness: (1) No taken node lies on a cycle. If one did, look at the first node of that cycle to be taken; its predecessor on the cycle had not been taken yet, so the edge from it still counted toward its in-degree, which contradicts the node being taken at in-degree 0. (2) If some nodes are never taken, each of them still has an incoming edge from another node that was never taken. Walking backward along such edges among finitely many untaken nodes must repeat a node, and that repetition is a directed cycle. So the answer is True exactly when the number of taken nodes is less than n.

Edge cases: a self-loop [u, u] adds to u's own in-degree, which only taking u could clear, so u is never taken and the answer is True. Duplicate copies of u -> v add k to v's in-degree and are all subtracted when u is taken, so they never create a false cycle. Isolated nodes and every disconnected component are covered because every in-degree-0 node seeds the work list, not only node 0. The procedure is iterative, so a very long path cannot overflow a recursion stack. Each node is appended at most once, so the work list never holds more than n entries.

Time complexity:
O(n + m), where m = len(edges)
Space complexity:
O(n + m)