受限条件下可到达节点的数目

难度: Medium

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间存在一条边。另给你一个整数数组 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⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges 表示一棵有效的树
1 <= restricted.length < n
1 <= restricted[i] < n
restricted 中的所有值 互不相同

Submission

运行时间: 123 ms

内存: 59.6 MB

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        g = defaultdict(list)
        r = set(restricted)
        for f, t in edges:
            if f not in r and t not in r:
                g[f].append(t)
                g[t].append(f)

        def dfs(v, fa):
            cnt = 1
            for n in g[v]:
                if n != fa:
                    cnt += dfs(n, v)
            return cnt
        return dfs(0, -1)

Explain

题解采用了深度优先搜索（DFS）的方法来解决该问题。首先，通过使用图（以邻接表的形式）来表示树的结构，从而避免访问受限节点。然后，从节点0开始，递归地遍历所有可到达的节点，并计算可到达节点的总数。在建图过程中，如果边的任一端点是受限节点，则该边不被添加到图中。DFS函数通过递归的方式访问所有子节点（排除了父节点以防止返回），并累计可以到达的节点数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        g = defaultdict(list)
        r = set(restricted)
        # 构建图，过滤掉连接受限节点的边
        for f, t in edges:
            if f not in r and t not in r:
                g[f].append(t)
                g[t].append(f)

        def dfs(v, fa):
            cnt = 1  # 包括当前节点
            for n in g[v]:
                if n != fa:  # 避免向父节点回溯
                    cnt += dfs(n, v)
            return cnt
        return dfs(0, -1)  # 从节点0开始DFS，-1作为虚拟父节点

Explore

在树或稀疏图的情况下，选择邻接表而不是邻接矩阵可以更加高效。邻接表相比于邻接矩阵，可以节省大量空间，尤其是当图中边的数量远少于节点数的平方时。此外，使用邻接表，可以更快地遍历到每个节点的直接邻居，因为它直接存储了每个节点的邻接节点，而不是存储整个节点间的关系矩阵，这在DFS等图遍历算法中特别有用，可以提高效率。

在DFS过程中，为了避免重复访问节点，通常会使用一个标记（如访问数组或集合）来记录哪些节点已被访问。在题解中，通过传递父节点的方法来避免回到父节点，从而防止无限循环，这种方法特别适用于树结构，因为树中任意两个节点间只有唯一路径，即不存在环。每次从一个节点向其子节点递归时，都会排除向回到该节点的父节点的可能，确保每个节点只被访问一次。

在DFS函数中，`fa`参数代表当前节点的父节点。这个参数的主要作用是防止在遍历过程中返回到父节点，从而避免造成无限循环。在树（特别是无向树）中，每个节点都可以通过任意一条边连接到其邻居节点，如果不记录父节点，节点在递归过程中可能会反复访问父节点，导致错误的循环递归。因此，通过记录每个节点的父节点（`fa`），可以在每次递归调用时检查并跳过向父节点的访问，确保DFS的正确进行。