长兴建设局网站,海南seo快速排名优化多少钱,烟台网站建设服务,网站域名 格式目录 2368. 受限条件下可到达节点的数目
题目描述#xff1a;
实现代码与解析#xff1a;
DFS
原理思路#xff1a; 2368. 受限条件下可到达节点的数目
题目描述#xff1a; 现有一棵由 n 个节点组成的无向树#xff0c;节点编号从 0 到 n - 1 #xff0c;共有 n - …目录 2368. 受限条件下可到达节点的数目
题目描述
实现代码与解析
DFS
原理思路 2368. 受限条件下可到达节点的数目
题目描述 现有一棵由 n 个节点组成的无向树节点编号从 0 到 n - 1 共有 n - 1 条边。
给你一个二维整数数组 edges 长度为 n - 1 其中 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 105edges.length n - 1edges[i].length 20 ai, bi nai ! biedges 表示一棵有效的树1 restricted.length n1 restricted[i] nrestricted 中的所有值 互不相同
实现代码与解析
DFS
class Solution {public final int N (int)2e5 10;// 邻接表int[] h new int[N], e new int[N * 2], ne new int[N * 2];int idx;// 连边方法public void add(int a, int b) {e[idx] b; ne[idx] h[a]; h[a] idx;} public int reachableNodes(int n, int[][] edges, int[] restricted) {Arrays.fill(h, -1); // 别忘了// 构成邻接表for (int[] e: edges) {int a e[0];int b e[1];add(a, b);add(b, a);}// set记录被标记的节点SetInteger set new HashSet();for (int t: restricted) {set.add(t);}// 从0节点dfs遍历int res dfs(0, -1, set);return res;}public int dfs(int cur, int f, SetInteger set) {int count 0;for (int i h[cur]; i ! -1; i ne[i]) {int j e[i];if (j ! f !set.contains(j)) {count dfs(j, cur, set);}}count;return count;}
}
原理思路 简单的dfs从0开始遍历即可统计可以走到的节点的个数。set用于记录受限制的节点作为递归条件。
