Medium

题目描述

有一个包含 n 个节点的无向树，节点编号从 0 到 n - 1，共有 n - 1 条边。

给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。同时给你一个整数数组 restricted 表示受限制的节点。

返回在不访问受限制节点的情况下，从节点 0 出发能够到达的节点数目的最大值。

注意节点 0 不会是受限制的节点。

示例 1：

输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出：4
解释：上图显示了这棵树。
我们有 [0,1,2,3] 是从节点 0 出发在不访问受限制节点的情况下唯一可以到达的节点。

示例 2：

输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出：3
解释：上图显示了这棵树。
我们有 [0,5,6] 是从节点 0 出发在不访问受限制节点的情况下唯一可以到达的节点。

约束条件：

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges 表示一个有效的树
  • 1 <= restricted.length < n
  • 1 <= restricted[i] < n
  • restricted 的所有值都是唯一的

解题思路

这道题要求从节点 0 出发，在不经过受限制节点的情况下，统计能够访问的节点数量。

解题思路：

  1. 图的构建：首先需要根据 edges 构建邻接表表示的无向图，方便后续遍历。

  2. 标记受限节点：将 restricted 数组中的节点标记为不可访问，可以使用哈希集合快速查询。

  3. 图遍历：从节点 0 开始进行 DFS 或 BFS 遍历，在遍历过程中：

    • 跳过已访问的节点
    • 跳过受限制的节点
    • 对每个可访问的节点进行计数

  4. 计数统计：遍历过程中统计访问到的节点数量即为答案。

算法选择：

  • DFS（深度优先搜索）：递归实现简洁，适合树结构
  • BFS（广度优先搜索）：迭代实现，内存使用更可控

两种方法的时间复杂度都是 O(n)，空间复杂度也都是 O(n)。这里推荐使用 DFS，因为代码更简洁直观。

核心步骤：

  1. 构建邻接表
  2. 创建受限节点的哈希集合
  3. 从节点 0 开始 DFS，计数可达节点
  4. 返回计数结果

代码实现

class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        // 构建邻接表
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        // 标记受限节点
        unordered_set<int> restrictedSet(restricted.begin(), restricted.end());
        
        // DFS遍历计数
        vector<bool> visited(n, false);
        return dfs(graph, restrictedSet, visited, 0);
    }
    
private:
    int dfs(vector<vector<int>>& graph, unordered_set<int>& restrictedSet, 
            vector<bool>& visited, int node) {
        visited[node] = true;
        int count = 1;
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor] && restrictedSet.find(neighbor) == restrictedSet.end()) {
                count += dfs(graph, restrictedSet, visited, neighbor);
            }
        }
        
        return count;
    }
};

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        # 构建邻接表
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        # 标记受限节点
        restricted_set = set(restricted)
        
        # DFS遍历计数
        visited = [False] * n
        
        def dfs(node):
            visited[node] = True
            count = 1
            
            for neighbor in graph[node]:
                if not visited[neighbor] and neighbor not in restricted_set:
                    count += dfs(neighbor)
            
            return count
        
        return dfs(0)

public class Solution {
    public int ReachableNodes(int n, int[][] edges, int[] restricted) {
        // 构建邻接表
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (int[] edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        // 标记受限节点
        HashSet<int> restrictedSet = new HashSet<int>(restricted);
        
        // DFS遍历计数
        bool[] visited = new bool[n];
        return Dfs(graph, restrictedSet, visited, 0);
    }
    
    private int Dfs(List<int>[] graph, HashSet<int> restrictedSet, bool[] visited, int node) {
        visited[node] = true;
        int count = 1;
        
        foreach (int neighbor in graph[node]) {
            if (!visited[neighbor] && !restrictedSet.Contains(neighbor)) {
                count += Dfs(graph, restrictedSet, visited, neighbor);
            }
        }
        
        return count;
    }
}

var reachableNodes = function(n, edges, restricted) {
    // 构建邻接表
    const graph = Array(n).fill().map(() => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    // 标记受限节点
    const restrictedSet = new Set(restricted);
    
    // DFS遍历计数
    const visited = new Array(n).fill(false);
    
    function dfs(node) {
        visited[node] = true;
        let count = 1;
        
        for (const neighbor of graph[node]) {
            if (!visited[neighbor] && !restrictedSet.has(neighbor)) {
                count += dfs(neighbor);
            }
        }
        
        return count;
    }
    
    return dfs(0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有可达节点，最多访问 n 个节点
空间复杂度O(n)邻接表存储图结构需要 O(n) 空间，递归调用栈深度最多为 n

相关题目