Title Description

Number of schemes to reconstruct a tree

thinking

Construct the tree and verify the legitimacy of the tree

The first is the second item in the description of scheme number condition in the title. If and only if it means that all number pairs in pairs have ancestor grandson relationship, and all nodes with ancestor grandson relationship are number pairs in pairs.
Suppose the number of nodes in the tree is n, the number of pairs containing node X in pairs is degree[x], and the ancestor and descendant node set of node x is adj[x].
First, the root node is the ancestor of all other nodes in the tree. The root node and all other nodes can form a number pair. Assuming that the root node is root, then degree[root]=n-1. Secondly, for the number pairs [xi, yi] in pairs, if xi is the ancestor of yi, it must satisfy degree [xi] > = degree [yi]. If yj is the descendant node of yi, yj must also be the descendant node of xi; If yj is the ancestor node of yi, yj is either the ancestor node of xi or the descendant node; In either case, it must meet the requirements of degree [xi] > = degree [yj]. If xi is the ancestor of yi, then adj[yi] ∈ adj[xi].
In addition, for the number pairs [xi, yi] in pairs, if xi is the ancestor of yi and satisfies degree[xi] = degree[yi] and adj[xi] = adj[yi], all nodes of the path from xi to yi have only one child node. At this time, the number pair relationship contained in the nodes from xi to yi is the same. The nodes from xi to yi can exchange positions with each other without affecting the structure of the tree, so the number of schemes constituting the tree must not be unique at this time.
Therefore, for the number pairs [xi, yi] in pairs, we have the following conclusions:

• If degree [xi] > degree [yi], xi is the ancestor node of yi;
• If degree [yi] > degree [xi], yi is the ancestor node of xi;
• If degree[xi] = degree[yi], there may be many construction methods. yi is the ancestor of xi or xi is the ancestor of yi.

Through the above analysis conclusion, construct the tree and check whether the tree is legal.

• First, find the root node, and find the node satisfying degree[root] = n-1. If there is no root node, it is considered that it cannot form a legal tree, and 0 is returned.
• Using the above conclusions, check whether the constructed tree is legal, traverse each node nodei, find its ancestor parenti, and check whether adj[nodei] is a subset of adj[parenti]. Use degree [nodei] < = degree [parenti] to find all ancestor nodes belonging to nodei, and then successively detect whether they meet adj[nodei] ∈ adj[parenti]. If they do not meet the requirements, the constructed number is illegal and returns 0.
• In the actual detection process, all the ancestor nodes of node nodei are not detected, as long as the parent node of node nodei meets the requirements of subset inclusion. According to the above conclusion, if node x meets the minimum degree[x] and degree[x] > = degree [nodei], then the node found at this time is the parent node of node nodei. At this time, it is only necessary to detect whether the parent node meets the above requirements.
• Set the parent node of nodei as parent. If degree[nodei] = degree[parent], there are multiple tree construction methods, and 2 is returned.

Python implementation

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        adj = defaultdict(set)
        for x, y in pairs:
            adj[x].add(y)
            adj[y].add(x)
        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)
        if root == -1:
            return 0
        ans = 1
        for node, neighbours in adj.items():
            if node == root:
                continue
            curDegree = len(neighbours)
            parent = -1
            parentDegree = maxsize
            for neighbour in neighbours:
                if curDegree <= len(adj[neighbour]) < parentDegree:
                    parent = neighbour
                    parentDegree = len(adj[neighbour])
            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):
                return 0
            if curDegree == parentDegree:
                ans = 2
        return ans

Java implementation

class Solution {
    public int checkWays(int[][] pairs) {
        Map<Integer, Set<Integer>> adj = new HashMap<Integer, Set<Integer>>();
        for (int[] p : pairs) {
            adj.putIfAbsent(p[0], new HashSet<Integer>());
            adj.putIfAbsent(p[1], new HashSet<Integer>());
            adj.get(p[0]).add(p[1]);
            adj.get(p[1]).add(p[0]);
        }
        /* Detect whether there is a root node*/
        int root = -1;
        Set<Map.Entry<Integer, Set<Integer>>> entries = adj.entrySet();
        for (Map.Entry<Integer, Set<Integer>> entry : entries) {
            int node = entry.getKey();
            Set<Integer> neighbours = entry.getValue();
            if (neighbours.size() == adj.size() - 1) {
                root = node;
            }
        }
        if (root == -1) {
            return 0;
        }

        int res = 1;
        for (Map.Entry<Integer, Set<Integer>> entry : entries) {
            int node = entry.getKey();
            Set<Integer> neighbours = entry.getValue();
            if (node == root) {
                continue;
            }
            int currDegree = neighbours.size();
            int parent = -1;
            int parentDegree = Integer.MAX_VALUE;

            /* Find the parent node of node according to the size of degree */
            for (int neighbour : neighbours) {
                if (adj.get(neighbour).size() < parentDegree && adj.get(neighbour).size() >= currDegree) {
                    parent = neighbour;
                    parentDegree = adj.get(neighbour).size();
                }
            }
            if (parent == -1) {
                return 0;
            }

            /* Detect whether neighbors are a subset of adj[parent] */
            for (int neighbour : neighbours) {
                if (neighbour == parent) {
                    continue;
                }
                if (!adj.get(parent).contains(neighbour)) {
                    return 0;
                }
            }
            if (parentDegree == currDegree) {
                res = 2;
            }
        }
        return res;
    }
}