Graph, DFS
Given an undirected graph and its spanning tree T and starting node 0, return true if the spanning tree T is a valid traversal tree by some DFS on G from starting node 0, otherwise return false.
Input: line 0: [number of nodes V] [number of edges E] the following V lines: each line contains a space separated numbers indicating adjacency list of node 0, 1, 2, ... 1 line: the starting node label V-1 lines: the V-1 tree edges Output: true if the spanning tree is valid DFS traversal tree false otherwise
Starter code in C++ that reads the input
Example 1
Input: 3 3 1 2 0 2 0 1 0 0 1 0 2 Output: false Explanation: For this small problem there is only two valid DFS traversal tree starting from node 0 1. 0-1, 1-2 2. 0-2, 2-1 The given tree 0-1, 0-2 is not one of the the two.
Example 2
Input: 3 3 1 2 0 2 0 1 0 0 2 1 2 Output: true
Example 3
Input: 3 3 1 2 0 2 0 1 0 0 1 1 2 Output: true