FastPrepFind Graph Roots and Traverse with DFS

Find Graph Roots and Traverse with DFS

NVIDIA logoNVIDIA● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Given a directed graph with vertices 0 through n-1 and edges [from,to], find every vertex with zero indegree and traverse the entire graph using depth-first search.

Return a two-row array. The first row contains all zero-indegree roots in ascending order. The second row contains the DFS first-visit order. Start a DFS at each root in ascending order, then start one at each still-unvisited vertex in ascending order so cycles and disconnected components are covered. At each vertex, visit its distinct outgoing neighbors in ascending order. Duplicate edges have no additional effect.

A graph may have no root, one root, or several roots. If n=0, return [[],[]].

Function

rootsAndDfsOrder(n: int, edges: int[][]) → int[][]

Examples

Example 1

n = 5edges = [[0,2],[0,1],[2,3],[1,3]]return = [[0,4],[0,1,3,2,4]]

Vertices 0 and 4 have zero indegree. DFS from 0 visits its sorted neighbors before the isolated root 4.

Example 2

n = 3edges = [[0,1],[1,0],[1,2]]return = [[],[0,1,2]]

The cycle between 0 and 1 leaves no zero-indegree root. The fallback starts at vertex 0.

Example 3

n = 0edges = []return = [[],[]]

An empty graph has neither roots nor visited vertices.

Constraints

  • 0 <= n <= 20000.
  • 0 <= edges.length <= 50000.
  • Each edge has exactly two vertices in [0,n-1].
  • Self-loops, cycles, and duplicate edges are allowed.

More NVIDIA problems

See NVIDIA hiring insights
public int[][] rootsAndDfsOrder(int n, int[][] edges) {
    // Write your code here.
}
n5
edges[[0,2],[0,1],[2,3],[1,3]]
expected[[0,4],[0,1,3,2,4]]
Checking account…