Beyond Big O

Dependency cycle detection

Dependency cycle detection

Medium

Your task

  • Check whether a directed dependency graph contains a cycle.
  • Return true if any cycle exists, otherwise false.
  • Check every component, including nodes you cannot reach from node 0.

Required API

  • HasDependencyCycle
    func HasDependencyCycle(count int, edges [][2]int) bool

Behavior

  • An edge [from, to] points from one node to another.
  • A self-loop is a cycle.
  • Repeated identical edges are valid and do not create a cycle by themselves.
  • An empty graph has no cycle.
  • Leave the edge list unchanged and keep separate calls independent.
  • Aim for O(count + edges) time using only the standard library.

Constraints

  • The input is valid: count is 0–200 and identifies nodes 0 through count - 1.
  • There are 0–500 edges, each containing two valid node indices.
Notes and example notation

Examples use {"count": ..., "edges": [[from, to], ...]}.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · empty

Arguments
count
0
edges
[]
Expected return
false
Test data
Input
{"count":0,"edges":[]}
Expected output
false

Example 2 · chain

Arguments
count
4
edges
[
  [
    0,
    1
  ],
  [
    1,
    2
  ],
  [
    2,
    3
  ]
]
Expected return
false
Test data
Input
{"count":4,"edges":[[0,1],[1,2],[2,3]]}
Expected output
false

Example 3 · cycle

Arguments
count
3
edges
[
  [
    0,
    1
  ],
  [
    1,
    2
  ],
  [
    2,
    0
  ]
]
Expected return
true
Test data
Input
{"count":3,"edges":[[0,1],[1,2],[2,0]]}
Expected output
true

Example 4 · disconnected cycle

Arguments
count
5
edges
[
  [
    0,
    1
  ],
  [
    2,
    3
  ],
  [
    3,
    4
  ],
  [
    4,
    2
  ]
]
Expected return
true
Test data
Input
{"count":5,"edges":[[0,1],[2,3],[3,4],[4,2]]}
Expected output
true
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…