Number Of Ways To Reconstruct A Tree
1. Xi < Yi. 2. There is no duplicate in the ‘PAIRS’ array.
1. The nodes of the tree must be present in the ‘PAIRS’ array. 2. A pair [Xi, Yi] exists in pairs if and only if Xi is an ancestor of Yi or Yi is an ancestor of Xi.
1. 0, if there is no way to reconstruct a tree. 2. 1, if there is exactly 1 way. 3. 2, if there is more than 1 way.
1. The tree does not necessarily have to be a binary tree. 2. A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root. 3. An ancestor of a node is any node on the path from the root to that node. The root has no ancestors.
The first line of the input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains a single integer ‘N’, as described in the problem statement. Then next ‘N’ lines contain two space-separated integers denoting the pair [Xi, Yi], as described in the problem statement.
For each test case, print a single line containing either ‘0’,’1’, or ‘2’ depending on the number of ways to reconstruct the rooted tree. The output of every test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10 1 <= N <= 10 ^ 5 1 <= Xi < Yi <= 500 Where ‘T’ denotes the number of test cases and ‘N’ denotes the size of ‘PAIRS’. Time Limit: 1 sec.
Ninja And The Class Room
Distance to a Cycle in Undirected Graph
Ninja And The Strictly Increasing Array