苏州网站建设套餐,河北哪里在建设,网站500m空间够用吗,做网站的几个必要步骤#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ BFS 求解思路 实现代码 运行结果 共勉 题目链接
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 105 edges.length n - 1 edges[i].length 2 0 ai, bi n ai ! bi edges 表示一棵有效的树 1 restricted.length n 1 restricted[i] n restricted 中的所有值 互不相同 求解思路实现代码运行结果 ⚡ BFS 求解思路
先将这棵无向树建立起来然后通过BFS来找到可以到达的最多节点的数目在遍历的过程如果遇到restricted数组中限制的节点直接跳过否则直接加入计数加1同时不要忘记将当前节点标记为走过的状态继续该过程。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {public int reachableNodes(int n, int[][] edges, int[] restricted) {HashSetInteger set new HashSet();for (int v : restricted)set.add(v);ArrayListInteger[] edge new ArrayList[n];Arrays.setAll(edge, e - new ArrayListInteger());for (int[] e : edges) {int from e[0], to e[1];edge[from].add(to);edge[to].add(from);}int cnt 1;DequeInteger queue new LinkedList();queue.addLast(0);set.add(0);while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {int cur queue.pollFirst();for (int next : edge[cur]) {if (!set.contains(next)) {queue.addLast(next);set.add(next);cnt;}}}}return cnt;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
