InternDoor

Is there a loop in a one-way graph?

Mediumgraphs · topological sort · depth-first search

Reported in interviews at (where)

A directed graph has n vertices numbered 0 to n - 1. Each edges[i] = [u, v] is a one-way edge from u to v. The same edge may be listed twice, and an edge from a vertex to itself is allowed.

Return true if you can start at some vertex, follow edges in their direction, and come back to where you started. Return false otherwise.

Example 1
Input
n = 4
edges = [[0,1],[1,2],[2,0],[2,3]]
Output
true

0 to 1 to 2 and back to 0.

Example 2
Input
n = 3
edges = [[0,1],[0,2],[2,1]]
Output
false

Vertex 1 is reached two ways, but no path leads back to where it began.

Example 3
Input
n = 2
edges = [[1,1]]
Output
true

An edge from 1 to itself is a loop of length one.

Limits

  • 1 <= n <= 5000
  • 0 <= edges.length <= 20000
  • 0 <= u, v < n

Hints

Hint 1

Count each vertex's incoming edges. Repeatedly take a vertex with none left and remove its outgoing edges.

Hint 2

If every vertex gets taken, there is no loop. Vertices that are never taken sit on a loop or behind one.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.