Leetcode 2368. 受限条件下可到达节点的数目
现有一棵由 n 个节点组成的无向树,节点编号从 0 到 n - 1 ,共有 n - 1 条边。
给你一个二维整数数组 edges ,长度为 n - 1 ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。
在不访问受限节点的前提下,返回你可以从节点_ 0 到达的 最多 节点数目。_
注意,节点 0 不 会标记为受限节点。
用 list 数组保存每个节点可到达的节点,用一个数组保存节点是否可访问,其中1
表示可访问,-1
表示受限制。
从 0
开始深度优先搜索,把节点的访问性设为 1
,然后深度优先搜索遍历可到达的节点,如果节点可访问性已经是 1
或-1
,就不进行处理。
完整代码
class Solution {int[] visit;List<Integer>[] list;public int reachableNodes(int n, int[][] edges, int[] restricted) {list = new List[n];visit = new int[n];for (int i = 0; i < n; i++) {list[i] = new ArrayList<>();}for (int[] edge : edges) {list[edge[0]].add(edge[1]);list[edge[1]].add(edge[0]);}for (int num : restricted) {visit[num] = -1;}dfs(0);int res = 0;for (int i = 0; i < n; i++) {if (visit[i] == 1) res++;}return res;}public void dfs(int index) {visit[index] = 1;for (Integer num : list[index]) {if (visit[num] == 0) dfs(num);}}
}