1719. Number Of Ways To Reconstruct A Tree

Problem

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

• There are no duplicates.

• xi < yi

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

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

  Example 1:

Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.

Example 2:

Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3:

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.

  Constraints:

• 1 <= pairs.length <= 105

• 1 <= xi < yi <= 500

• The elements in pairs are unique.

Solution

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var checkWays = function(pairs) {
    var map = {};
    for (var i = 0; i < pairs.length; i++) {
        var [x, y] = pairs[i];
        if (!map[x]) map[x] = [];
        if (!map[y]) map[y] = [];
        map[x].push(y);
        map[y].push(x);
    }
    var nums = Object.keys(map).sort((a, b) => map[a].length - map[b].length);
    var visited = {};
    var result = 1;
    for (var i = nums.length - 1; i >= 0; i--) {
        var num = nums[i];
        var parentDegree = Number.MAX_SAFE_INTEGER;
        var parent = -1;
        for (var j = 0; j < map[num].length; j++) {
            var n = map[num][j];
            if (visited[n] && map[n].length >= map[num].length && map[n].length < parentDegree) {
                parentDegree = map[n].length;
                parent = n;
            }
        }
        visited[num] = true;
        if (parent === -1) {
            if (map[num].length === nums.length - 1) continue;
            return 0;
        }
        for (var j = 0; j < map[num].length; j++) {
            if (map[num][j] !== parent && !map[parent].includes(map[num][j])) {
                return 0;
            }
        }
        if (map[parent].length === map[num].length) {
            result = 2;
        }
    }
    return result;
};

Explain:

see https://leetcode.com/problems/number-of-ways-to-reconstruct-a-tree/solutions/1009393/c-o-nlogn-soln-with-comments-descriptive-variable-naming-time-space-complexity-analysis/

Complexity:

• Time complexity : O(n ^ 2).
• Space complexity : O(n ^ 2).