Number Of Ways To Reconstruct A Tree

Posted: 18 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given an array ‘PAIRS’ consisting of ‘N’ pairs, where PAIRS[i] = [Xi, Yi] such that:

1. Xi < Yi.

2. There is no duplicate in the ‘PAIRS’ array.

You have to determine the number of ways to reconstruct a rooted tree that satisfies the following conditions:

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.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

You should return:
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.

Note:

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.
Input Format:
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.
Output Format:
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.
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 <= 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.
Approach 1
  • The main idea in this problem is that if we consider a node as a root then it must be paired with all of its descendants and its ancestors. So a parent's pairings will always contain a child's pairings.
  • So, we will create an adjacency list from the input pairs and we will reconstruct the tree from top to bottom.
  • Now if there are ‘M’ different nodes in the tree, then the root of the tree must have the degree = ‘M’ - 1. Therefore, if the node with the highest degree has its degree less than ‘M’ - 1 then the answer is 0 because there is no node that can be the root of the tree.
  • So, we will move from top to bottom by choosing the nodes with the highest degree first, and then we will choose a node with the least degree from the current node’s adjacency which is visited before to be the parent of the current node.
  • Now the parent’s adjacency must contain the current node’s adjacency, if this is not true the answer will be 0.
  • Now for more than 1 answer, if at any moment the current node and its parent has the same degree then there will be multiple trees possible as we can consider these nodes in any order.
  • So, if we can visit all nodes successfully then the answer is surely 1, but if we found a node such that it’s degree is equal to its parent’s degree, then there are multiple answers possible and hence the answer will be 2.
Try Problem