Hard

题目描述

有 n 个城市，编号从 1 到 n。给你一个大小为 n-1 的数组 edges，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。任意两个城市之间有且仅有一条路径。换句话说，所有城市形成了一棵树。

子树是城市的一个子集，其中任何城市都可以通过该子集中的其他城市和连接该子集中城市的边到达该子集中的任何其他城市。如果两个子树中的城市集合不同，则认为这两个子树不同。

对于 d 从 1 到 n-1，找到子树中任意两个城市之间的最大距离 正好为 d 的子树数目。

返回一个大小为 n-1 的数组，其中第 d 个元素（从 1 开始编号）是子树中任意两个城市之间的最大距离正好为 d 的子树数目。

请注意，两个城市之间的距离就是连接它们的路径上的边数。

示例 1:

输入: n = 4, edges = [[1,2],[2,3],[2,4]]
输出: [3,4,0]
解释:
子树 {1,2}, {2,3} 和 {2,4} 的最大距离为 1。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 的最大距离为 2。
没有子树的任意两个节点之间的最大距离为 3。

示例 2:

输入: n = 2, edges = [[1,2]]
输出: [1]

示例 3:

输入: n = 3, edges = [[1,2],[2,3]]
输出: [2,1]

提示:

  • 2 <= n <= 15
  • edges.length == n-1
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • 所有 (ui, vi) 都是不同的。

解题思路

这是一道经典的树形DP和位运算组合题。由于n最大为15，我们可以使用位掩码枚举所有可能的子树。

核心思路：

  1. 子树枚举：使用位掩码从1到2^n-1枚举所有可能的城市子集
  2. 连通性检查：对每个子集，检查是否形成连通的子树：
    • 统计子集中包含的边数
    • 如果子集有k个城市，连通的子树必须有k-1条边
  3. 最大距离计算：对连通的子树，计算任意两点间的最大距离（直径）
  4. 统计结果：将每个有效子树按其直径进行分类计数

算法步骤：

  • 预处理：构建邻接表，使用Floyd算法计算所有点对间距离
  • 枚举：遍历所有可能的位掩码（子集）
  • 验证：检查子集是否构成连通子树
  • 计算：求出该子树的直径
  • 累计：将结果加入对应距离的计数器

时间复杂度优化： 可以通过DFS或BFS来验证连通性并计算直径，避免使用Floyd算法的额外开销。对于每个valid的子树，我们选择其中任意一点作为起点，BFS求出最远点，再从最远点BFS求直径。

代码实现

class Solution {
public:
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0] - 1].push_back(edge[1] - 1);
            graph[edge[1] - 1].push_back(edge[0] - 1);
        }
        
        vector<int> result(n - 1, 0);
        
        // 枚举所有可能的子集
        for (int mask = 1; mask < (1 << n); mask++) {
            vector<int> nodes;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    nodes.push_back(i);
                }
            }
            
            if (nodes.size() < 2) continue;
            
            // 检查连通性
            if (!isConnected(nodes, graph)) continue;
            
            // 计算直径
            int diameter = getDiameter(nodes, graph);
            if (diameter > 0 && diameter <= n - 1) {
                result[diameter - 1]++;
            }
        }
        
        return result;
    }
    
private:
    bool isConnected(vector<int>& nodes, vector<vector<int>>& graph) {
        if (nodes.empty()) return false;
        
        unordered_set<int> nodeSet(nodes.begin(), nodes.end());
        unordered_set<int> visited;
        queue<int> q;
        
        q.push(nodes[0]);
        visited.insert(nodes[0]);
        
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            
            for (int next : graph[cur]) {
                if (nodeSet.count(next) && !visited.count(next)) {
                    visited.insert(next);
                    q.push(next);
                }
            }
        }
        
        return visited.size() == nodes.size();
    }
    
    int getDiameter(vector<int>& nodes, vector<vector<int>>& graph) {
        if (nodes.size() < 2) return 0;
        
        unordered_set<int> nodeSet(nodes.begin(), nodes.end());
        
        // 从任意点找最远点
        auto [farthest, dist] = bfs(nodes[0], nodeSet, graph);
        
        // 从最远点再找最远点，得到直径
        auto [_, diameter] = bfs(farthest, nodeSet, graph);
        
        return diameter;
    }
    
    pair<int, int> bfs(int start, unordered_set<int>& nodeSet, vector<vector<int>>& graph) {
        unordered_map<int, int> dist;
        queue<int> q;
        
        q.push(start);
        dist[start] = 0;
        
        int farthest = start;
        int maxDist = 0;
        
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            
            for (int next : graph[cur]) {
                if (nodeSet.count(next) && dist.find(next) == dist.end()) {
                    dist[next] = dist[cur] + 1;
                    q.push(next);
                    
                    if (dist[next] > maxDist) {
                        maxDist = dist[next];
                        farthest = next;
                    }
                }
            }
        }
        
        return {farthest, maxDist};
    }
};

class Solution:
    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque
        
        # 构建邻接表
        graph = defaultdict(list)
        for u, v in edges:
            graph[u-1].append(v-1)
            graph[v-1].append(u-1)
        
        result = [0] * (n - 1)
        
        # 枚举所有可能的子集
        for mask in range(1, 1 << n):
            nodes = []
            for i in range(n):
                if mask & (1 << i):
                    nodes.append(i)
            
            if len(nodes) < 2:
                continue
            
            # 检查连通性
            if not self.is_connected(nodes, graph):
                continue
            
            # 计算直径
            diameter = self.get_diameter(nodes, graph)
            if 1 <= diameter <= n - 1:
                result[diameter - 1] += 1
        
        return result
    
    def is_connected(self, nodes, graph):
        if not nodes:
            return False
        
        node_set = set(nodes)
        visited = set()
        queue = deque([nodes[0]])
        visited.add(nodes[0])
        
        while queue:
            cur = queue.popleft()
            for next_node in graph[cur]:
                if next_node in node_set and next_node not in visited:
                    visited.add(next_node)
                    queue.append(next_node)
        
        return len(visited) == len(nodes)
    
    def get_diameter(self, nodes, graph):
        if len(nodes) < 2:
            return 0
        
        node_set = set(nodes)
        
        # 从任意点找最远点
        farthest, dist = self.bfs(nodes[0], node_set, graph)
        
        # 从最远点再找最远点，得到直径
        _, diameter = self.bfs(farthest, node_set, graph)
        
        return diameter
    
    def bfs(self, start, node_set, graph):
        from collections import deque
        
        dist = {start: 0}
        queue = deque([start])
        
        farthest = start
        max_dist = 0
        
        while queue:
            cur = queue.popleft()
            for next_node in graph[cur]:
                if next_node in node_set and next_node not in dist:
                    dist[next_node] = dist[cur] + 1
                    queue.append(next_node)
                    
                    if dist[next_node] > max_dist:
                        max_dist = dist[next_node]
                        farthest = next_node
        
        return farthest, max_dist

public class Solution {
    public int[] CountSubgraphsForEachDiameter(int n, int[][] edges) {
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0] - 1].Add(edge[1] - 1);
            graph[edge[1] - 1].Add(edge[0] - 1);
        }
        
        int[] result = new int[n - 1];
        
        // 枚举所有可能的子集
        for (int mask = 1; mask < (1 << n); mask++) {
            var nodes = new List<int>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    nodes.Add(i);
                }
            }
            
            if (nodes.Count < 2) continue;
            
            // 检查连通性
            if (!IsConnected(nodes, graph)) continue;
            
            // 计算直径
            int diameter = GetDiameter(nodes, graph);
            if (diameter >= 1 && diameter <= n - 1) {
                result[diameter - 1]++;
            }
        }
        
        return result;
    }
    
    private bool IsConnected(List<int> nodes, List<int>[] graph) {
        if (nodes.Count == 0) return false;
        
        var nodeSet = new HashSet<int>(nodes);
        var visited = new HashSet<int>();
        var queue = new Queue<int>();
        
        queue.Enqueue(nodes[0]);
        visited.Add(nodes[0]);
        
        while (queue.Count > 0) {
            int cur = queue.Dequeue();
            foreach (int next in graph[cur]) {
                if (nodeSet.Contains(next) && !visited.Contains(next)) {
                    visited.Add(next);
                    queue.Enqueue(next);
                }
            }
        }
        
        return visited.Count == nodes.Count;
    }
    
    private int GetDiameter(List<int> nodes, List<int>[] graph) {
        if (nodes.Count < 2) return 0;
        
        var nodeSet = new HashSet<int>(nodes);
        
        // 从任意点找最远点
        var (farthest, dist) = BFS(nodes[0], nodeSet, graph);
        
        // 从最远点再找最远点，得到直径
        var (_, diameter) = BFS(farthest, nodeSet, graph);
        
        return diameter;
    }
    
    private (int, int) BFS(int start, HashSet<int> nodeSet, List<int>[] graph) {
        var dist = new Dictionary<int, int>();
        var queue = new Queue<int>();
        
        queue.Enqueue(start);
        dist[start] = 0;
        
        int farthest = start;
        int maxDist = 0;
        
        while (queue.Count > 0) {
            int cur = queue.Dequeue();
            foreach (int next in graph[cur]) {
                if (nodeSet.Contains(next) && !dist.ContainsKey(next)) {
                    dist[next] = dist[cur] + 1;
                    queue.Enqueue(next);
                    
                    if (dist[next] > maxDist) {
                        maxDist = dist[next];
                        farthest = next;
                    }
                }
            }
        }
        
        return (farthest, maxDist);
    }
}

var countSubgraphsForEachDiameter = function(n, edges) {
    const graph = Array(n + 1).fill(null).map(() => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const result = Array(n - 1).fill(0);
    
    for (let mask = 1; mask < (1 << n); mask++) {
        const cities = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                cities.push(i + 1);
            }
        }
        
        if (cities.length < 2) continue;
        
        if (isConnected(cities, graph)) {
            const maxDist = getMaxDistance(cities, graph);
            if (maxDist > 0 && maxDist <= n - 1) {
                result[maxDist - 1]++;
            }
        }
    }
    
    return result;
};

function isConnected(cities, graph) {
    if (cities.length === 0) return true;
    
    const citySet = new Set(cities);
    const visited = new Set();
    const queue = [cities[0]];
    visited.add(cities[0]);
    
    while (queue.length > 0) {
        const city = queue.shift();
        for (const neighbor of graph[city]) {
            if (citySet.has(neighbor) && !visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    
    return visited.size === cities.length;
}

function getMaxDistance(cities, graph) {
    let maxDist = 0;
    const citySet = new Set(cities);
    
    for (const start of cities) {
        const distances = bfs(start, citySet, graph);
        for (const dist of distances.values()) {
            maxDist = Math.max(maxDist, dist);
        }
    }
    
    return maxDist;
}

function bfs(start, citySet, graph) {
    const distances = new Map();
    const queue = [start];
    distances.set(start, 0);
    
    while (queue.length > 0) {
        const city = queue.shift();
        for (const neighbor of graph[city]) {
            if (citySet.has(neighbor) && !distances.has(neighbor)) {
                distances.set(neighbor, distances.get(city) + 1);
                queue.push(neighbor);
            }
        }
    }
    
    return distances;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目