1719. 重构一棵树的方案数

Hard

题目描述

给你一个数组 pairs，其中 pairs[i] = [xi, yi]，并且满足：

没有重复的数对
xi < yi

设 ways 为满足下述条件的有根树的数量：

树包含的节点值出现在 pairs 中
当且仅当 xi 是 yi 的祖先或者 yi 是 xi 的祖先时，数对 [xi, yi] 才存在于 pairs 中
注意：树不一定是二叉树

如果存在至少一个节点在两种方案中有不同的父节点，则认为两种方案不同。

如果 ways == 0，返回 0
如果 ways == 1，返回 1
如果 ways > 1，返回 2

有根树是具有单个根节点的树，所有边都从根向外定向。

节点的祖先是从根到该节点路径上的任意节点（不包括节点本身）。根没有祖先。

示例 1：

输入: pairs = [[1,2],[2,3]]
输出: 1
解释: 只有一棵有效的有根树，如上图所示。

示例 2：

输入: pairs = [[1,2],[2,3],[1,3]]
输出: 2
解释: 有多棵有效的有根树。其中三棵如上图所示。

示例 3：

输入: pairs = [[1,2],[2,3],[2,4],[1,5]]
输出: 0
解释: 没有有效的有根树。

约束条件：

1 <= pairs.length <= 10^5
1 <= xi < yi <= 500
pairs 中的元素是唯一的

解题思路

这是一道图论与树重构的题目。核心思想是从度数最大的节点开始，逐层构建树。

解题思路：

根节点识别：在一棵树中，根节点应该与所有其他节点都有连接关系。因此，度数最大的节点最可能是根节点。
度数约束：对于任意两个有连接关系的节点，父节点的度数必须大于等于子节点的度数。这是因为父节点需要连接到子节点能连接到的所有节点，还可能连接到更多节点。
递归构建：确定根节点后，移除根节点，在剩余的连通分量中重复这个过程。每次选择度数最大的节点作为当前子树的根。
唯一性判断：如果存在多个节点具有相同的最大度数，说明它们可以互换位置，因此方案数大于1。

算法流程：

统计每个节点的度数
用BFS/DFS的方式，每次找到度数最大的节点集合
如果最大度数节点超过1个，标记为多方案
验证父子关系的度数约束是否满足
递归处理子连通分量

代码实现

class Solution {
public:
    int checkWays(vector<vector<int>>& pairs) {
        unordered_map<int, unordered_set<int>> graph;
        
        // 构建邻接表
        for (auto& pair : pairs) {
            graph[pair[0]].insert(pair[1]);
            graph[pair[1]].insert(pair[0]);
        }
        
        // 获取所有节点
        vector<int> nodes;
        for (auto& [node, _] : graph) {
            nodes.push_back(node);
        }
        
        return dfs(nodes, graph);
    }
    
private:
    int dfs(vector<int>& nodes, unordered_map<int, unordered_set<int>>& graph) {
        if (nodes.size() <= 1) return 1;
        
        // 找到度数最大的节点
        int maxDegree = 0;
        vector<int> roots;
        
        for (int node : nodes) {
            int degree = 0;
            for (int other : nodes) {
                if (node != other && graph[node].count(other)) {
                    degree++;
                }
            }
            
            if (degree > maxDegree) {
                maxDegree = degree;
                roots.clear();
                roots.push_back(node);
            } else if (degree == maxDegree) {
                roots.push_back(node);
            }
        }
        
        // 根节点应该与所有其他节点相连
        if (maxDegree != nodes.size() - 1) return 0;
        
        int result = roots.size() > 1 ? 2 : 1;
        
        // 选择第一个根节点进行递归
        int root = roots[0];
        vector<int> remaining;
        for (int node : nodes) {
            if (node != root) remaining.push_back(node);
        }
        
        // 验证剩余节点间的连接
        for (int i = 0; i < remaining.size(); i++) {
            for (int j = i + 1; j < remaining.size(); j++) {
                int u = remaining[i], v = remaining[j];
                if (graph[u].count(v)) {
                    // u和v相连，检查度数约束
                    int degreeU = 0, degreeV = 0;
                    for (int node : nodes) {
                        if (node != u && graph[u].count(node)) degreeU++;
                        if (node != v && graph[v].count(node)) degreeV++;
                    }
                    // 度数小的不能是度数大的祖先
                    if (degreeU == degreeV) result = 2;
                }
            }
        }
        
        // 递归处理子树
        if (!remaining.empty()) {
            int subResult = dfs(remaining, graph);
            if (subResult == 0) return 0;
            if (subResult == 2) result = 2;
        }
        
        return result;
    }
};

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        from collections import defaultdict
        
        # 构建邻接表
        graph = defaultdict(set)
        for x, y in pairs:
            graph[x].add(y)
            graph[y].add(x)
        
        nodes = list(graph.keys())
        return self.dfs(nodes, graph)
    
    def dfs(self, nodes, graph):
        if len(nodes) <= 1:
            return 1
        
        # 找到度数最大的节点
        max_degree = 0
        roots = []
        
        for node in nodes:
            degree = sum(1 for other in nodes if other != node and other in graph[node])
            
            if degree > max_degree:
                max_degree = degree
                roots = [node]
            elif degree == max_degree:
                roots.append(node)
        
        # 根节点应该与所有其他节点相连
        if max_degree != len(nodes) - 1:
            return 0
        
        result = 2 if len(roots) > 1 else 1
        
        # 选择第一个根节点进行递归
        root = roots[0]
        remaining = [node for node in nodes if node != root]
        
        # 验证剩余节点间的连接
        for i in range(len(remaining)):
            for j in range(i + 1, len(remaining)):
                u, v = remaining[i], remaining[j]
                if v in graph[u]:
                    # u和v相连，检查度数约束
                    degree_u = sum(1 for node in nodes if node != u and node in graph[u])
                    degree_v = sum(1 for node in nodes if node != v and node in graph[v])
                    if degree_u == degree_v:
                        result = 2
        
        # 递归处理子树
        if remaining:
            sub_result = self.dfs(remaining, graph)
            if sub_result == 0:
                return 0
            if sub_result == 2:
                result = 2
        
        return result

public class Solution {
    public int CheckWays(int[][] pairs) {
        var graph = new Dictionary<int, HashSet<int>>();
        
        // 构建邻接表
        foreach (var pair in pairs) {
            if (!graph.ContainsKey(pair[0])) graph[pair[0]] = new HashSet<int>();
            if (!graph.ContainsKey(pair[1])) graph[pair[1]] = new HashSet<int>();
            graph[pair[0]].Add(pair[1]);
            graph[pair[1]].Add(pair[0]);
        }
        
        var nodes = graph.Keys.ToList();
        return DFS(nodes, graph);
    }
    
    private int DFS(List<int> nodes, Dictionary<int, HashSet<int>> graph) {
        if (nodes.Count <= 1) return 1;
        
        // 找到度数最大的节点
        int maxDegree = 0;
        var roots = new List<int>();
        
        foreach (int node in nodes) {
            int degree = nodes.Count(other => other != node && graph[node].Contains(other));
            
            if (degree > maxDegree) {
                maxDegree = degree;
                roots.Clear();
                roots.Add(node);
            } else if (degree == maxDegree) {
                roots.Add(node);
            }
        }
        
        // 根节点应该与所有其他节点相连
        if (maxDegree != nodes.Count - 1) return 0;
        
        int result = roots.Count > 1 ? 2 : 1;
        
        // 选择第一个根节点进行递归
        int root = roots[0];
        var remaining = nodes.Where(node => node != root).ToList();
        
        // 验证剩余节点间的连接
        for (int i = 0; i < remaining.Count; i++) {
            for (int j = i + 1; j < remaining.Count; j++) {
                int u = remaining[i], v = remaining[j];
                if (graph[u].Contains(v)) {
                    // u和v相连，检查度数约束
                    int degreeU = nodes.Count(node => node != u && graph[u].Contains(node));
                    int degreeV = nodes.Count(node => node != v && graph[v].Contains(node));
                    if (degreeU == degreeV) result = 2;
                }
            }
        }
        
        // 递归处理子树
        if (remaining.Count > 0) {
            int subResult = DFS(remaining, graph);
            if (subResult == 0) return 0;
            if (subResult == 2) result = 2;
        }
        
        return result;
    }
}

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var checkWays = function(pairs) {
    const adj = new Map();
    
    // Build adjacency list
    for (const [x, y] of pairs) {
        if (!adj.has(x)) adj.set(x, new Set());
        if (!adj.has(y)) adj.set(y, new Set());
        adj.get(x).add(y);
        adj.get(y).add(x);
    }
    
    const nodes = Array.from(adj.keys());
    
    // Sort by degree (descending)
    nodes.sort((a, b) => adj.get(b).size - adj.get(a).size);
    
    const parent = new Map();
    let ways = 1;
    
    for (let i = 0; i < nodes.length; i++) {
        const node = nodes[i];
        let p = -1;
        
        // Find parent among processed nodes
        for (let j = 0; j < i; j++) {
            if (adj.get(nodes[j]).has(node)) {
                p = nodes[j];
                break;
            }
        }
        
        parent.set(node, p);
        
        if (p !== -1) {
            // Check if all neighbors of node (except parent) are also neighbors of parent
            for (const neighbor of adj.get(node)) {
                if (neighbor !== p && !adj.get(p).has(neighbor)) {
                    return 0;
                }
            }
            
            // Check if there's ambiguity
            if (adj.get(node).size === adj.get(p).size) {
                ways = 2;
            }
        }
    }
    
    // Verify all pairs are covered
    const covered = new Set();
    
    function addAncestors(node, ancestors) {
        for (const ancestor of ancestors) {
            const pair = ancestor < node ? `${ancestor},${node}` : `${node},${ancestor}`;
            covered.add(pair);
        }
        
        const children = [];
        for (const [child, par] of parent) {
            if (par === node) {
                children.push(child);
            }
        }
        
        for (const child of children) {
            const newAncestors = new Set(ancestors);
            newAncestors.add(node);
            addAncestors(child, newAncestors);
        }
    }
    
    // Find root
    let root = -1;
    for (const node of nodes) {
        if (parent.get(node) === -1) {
            root = node;
            break;
        }
    }
    
    addAncestors(root, new Set());
    
    if (covered.size !== pairs.length) {
        return 0;
    }
    
    return ways;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构建邻接表	O(P)	O(N + P)
递归DFS	O(N³)	O(N²)
总体	O(N³)	O(N²)

其中 N 是节点数量，P 是 pairs 的数量。最坏情况下需要检查所有节点对的度数关系。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目