DFS Tree and Back Edges

Problem

Classify every undirected edge as a DFS tree edge or a non-tree edge.

Run a depth-first search that starts from each unvisited node in increasing order and explores neighbors in increasing order. An edge is a tree edge when it first discovers an unvisited node and a back edge when it meets an already visited node; each edge is classified once. Return [tree_count, back_count].

Hint

Track used edge indices so a shared edge is not counted twice after being traversed.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]]]

expected: [3,0]

case 2

in: [3,[[0,1],[1,2],[2,0]]]

expected: [2,1]

case 3

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: [3,1]

case 4

in: [5,[[0,1],[2,3]]]

expected: [2,0]

case 5

in: [4,[[0,1],[0,1],[2,3]]]

expected: [2,1]

Starter codePython

def dfs_tree_back_counts(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor