Leetcode 1719 - Number Of Ways To Reconstruct A Tree

Link to problem

Problem

You are given an array pairs, where pairs[i] = [xi, yi], and:

• There are no duplicates
• xi < y1

Let ways be the number of rooted trees that satisfy the following conditions:

• The tree consists of nodes whose values appeared in pairs.
• A pair [xi, yi] exists in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi.
• Note: the tree does not have to be a binary tree.

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

Return

• 0 if ways == 0
• 1 if ways == 1
• 2 if ways > 1

Approach

Definitely a Leetcode hard problem. But with the help of others on the internet (), I finally figured this out.

First lets look at the hints:

1. Think inductively. The first step is to get the root. Obviously, the root should be in pairs with all the nodes. If there isn’t exactly one such node, then there are 0 ways. This is quite intuitive, a parent node will appear in a pair with all of its descendant.

2. The number of pairs involving a node must be less than or equal to that number of its parent. Point 2 could be easily understand from point 1.

3. If it’s equal, then there is not exactly 1 way, because they can be swapped. Maybe some example will help to clear this, consider input of: {{1, 2}, {2, 3}, {1, 3}}. In this case every node involves with other two nodes in a pair, the number of pairs involved of each node is 2. Therefore, each node could be other two nodes’ ancestor or descendant. That is, the order of the nodes could be swapped. See figure1 for the tree. The figure is from leetcode, only shows three of the possible valid tree)

4. Recursively, given a set of nodes, get the node with the most pairs, then this must be a root and have no parents in the current set of nodes.

Figure 1. Example of tree that nodes could be swapped.

Solution

First we need to know how many pairs that a node are involved with. To do so, we could use adjacency list. Adjacency list records the node and its possible ancestors/descendants. Therefore, the degree of a node in this adjacency list means the pairs the node has appeared.

Secondly, we will need to get the nodes sorted by the pairs it appeared in. This could be done by using a std::priority_queue<std::pair<int, int>>, which the pair stores {number_of_pairs_the_node_appeared, node}. With the priority_queue, we could start from the node with most pairs (root) and gradually work towards the bottom (leaf nodes).

With the required data constructed, we could finally start to solve the problem:

1. Retrieve the node with most pairs (In this case, it would be the node with maximum degree).
2. From the visited node (we could use an unordered_set set to do this), find the node with minimum degree as “parent node”. If we could not find such node and the node is not root, return 0 as we could not place the node in the tree.
3. Mark the processed node as visited.
4. If the visited node found has a degree same as the current node, there could be multiple ways of forming the tree. However, we could not return 2 directly as there are still possibilities that the tree turn out to be invalid as we process throught the rest of the nodes.
5. Check the if the parent node is adjacent to the current node, if it is not, return 0.
6. Continue the process until the nodes have all been processed.

Implementation

class Solution {
public:
	int checkWays(std::vector<std::vector<int>>& pairs) {
		std::unordered_map<int, std::unordered_set<int>> adjacencyList;
		std::priority_queue<std::pair<int, int>> nodeDegree;
		std::unordered_set<int> visited;

		bool isMultipleValid = false;

		// build adjancency list
		for (auto p: pairs) {
			adjacencyList[p[0]].emplace(p[1]);
			adjacencyList[p[1]].emplace(p[0]);
		}

		for (auto& p: adjacencyList) {
			nodeDegree.push({p.second.size(), p.first});
		}

		int nodeSize = adjacencyList.size();

		while (!nodeDegree.empty()) {
			auto degree = nodeDegree.top().first;
			auto node = nodeDegree.top().second;
			nodeDegree.pop();

			int parentNode = 0, parentDegree = nodeSize + 1;
			if (!visited.empty()) {
				for (auto v: adjacencyList[node]) {
					if (visited.find(v) != visited.end() &&
						adjacencyList[v].size() < parentDegree) {
						parentNode = v;
						parentDegree = adjacencyList[v].size();
					}
				}
			}

			visited.insert(node);

			if (parentNode == 0) {
				// root node!!
				if (visited.size() != 1) return 0;
				else continue;
			}

			if (degree == parentDegree) {
				isMultipleValid = true;
			}

			for (auto adj: adjacencyList[node]) {
				if (adj == parentNode) continue;

				if (adjacencyList[parentNode].find(adj) ==
					adjacencyList[parentNode].end())
					return 0;
			}

		}

		return (isMultipleValid)? 2: 1;
	}
};