Last Updated: 8 Apr, 2021
Restore Array
Moderate
Asked in company
Ninja was having an array ‘NUMS’ of size ‘N’ having unique elements, but due to his fight with Evil, he lost his array.
You are given a 2D array ‘ARR’ of size N - 1 where ARR[ i ]=[ a, b ], indicating that a and b are adjacent in nums array.
Every adjacent pair {a,b} in nums array will exist in ‘ARR’ array as either [a,b] or [b,a].
Help the ninja to restore its num array.
Input Format:
The first line contains ‘T,’ denoting the number of test cases.
The first line of the test case contains a single integer ‘N’ denoting the size of the ‘NUMS’ array.
The following N - 1 lines contain two space-separated integers denoting the i-th element of ARR[i].
Output Format:
For each test case, print a single line containing 'N' space-separated integers denoting any possible answer array elements.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= ’T’ <= 10
1 <= ‘N’<= 5000
1 <= ARR[i][0], ARR[i][1] <= 10 ^ 6
Where ‘i’ varies from 1 to ‘N’ - 1 and ‘N’ is the length of the array ‘nums’.
Time Limit: 1 sec.
Approaches
The main idea is first create edges between adjacent nodes and then do the dfs traversal from the vertex with inDegree 1 as the vertex with inDegree 1 means it has only one adjacent element to it in nums array so it must be present at the first position since the element at the first position has only one element adjacent to it.
Algorithm :
- Create edges between adjacent elements from ‘arr’ array and make an adjacency list for this.
- Find the node with inDegree 1.
- Start the dfs traversal from the node with inDegree 1.
- While doing dfs traversal store all the nodes in a list.
- After dfs traversal returns the list which stores nodes.
Similar problems