【LeetCode:2368. 受限条件下可到达节点的数目 + BFS】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，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) {
        HashSet<Integer> set = new HashSet<>();
        for (int v : restricted)
            set.add(v);
        ArrayList<Integer>[] edge = new ArrayList[n];
        Arrays.setAll(edge, e -> new ArrayList<Integer>());
        for (int[] e : edges) {
            int from = e[0], to = e[1];
            edge[from].add(to);
            edge[to].add(from);
        }
        int cnt = 1;
        Deque<Integer> 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;
    }
}