西宁微信网站建设需要多少钱,行牛建站,为什么网站显示正在建设,网络营销形式Leetcode 2368. 受限条件下可到达节点的数目 现有一棵由 n 个节点组成的无向树#xff0c;节点编号从 0 到 n - 1 #xff0c;共有 n - 1 条边。 给你一个二维整数数组 edges #xff0c;长度为 n - 1 #xff0c;其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间存在一…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;ListInteger[] 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);}}
}
