🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風(fēng)和煒，CSDN-Java領(lǐng)域優(yōu)質(zhì)創(chuàng)作者🏆，保研|國家獎學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享💎💎💎
🌲 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 2368. 受限條件下可到達(dá)節(jié)點的數(shù)目

? 題目描述

現(xiàn)有一棵由 n 個節(jié)點組成的無向樹，節(jié)點編號從 0 到 n - 1 ，共有 n - 1 條邊。

給你一個二維整數(shù)數(shù)組 edges ，長度為 n - 1 ，其中 edges[i] = [ai, bi] 表示樹中節(jié)點 ai 和 bi 之間存在一條邊。另給你一個整數(shù)數(shù)組 restricted 表示 受限 節(jié)點。

在不訪問受限節(jié)點的前提下，返回你可以從節(jié)點 0 到達(dá)的 最多 節(jié)點數(shù)目。

注意，節(jié)點 0 不 會標(biāo)記為受限節(jié)點。

示例 1：

輸入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
輸出：4
解釋：上圖所示正是這棵樹。
在不訪問受限節(jié)點的前提下，只有節(jié)點 [0,1,2,3] 可以從節(jié)點 0 到達(dá)。
示例 2：

輸入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
輸出：3
解釋：上圖所示正是這棵樹。
在不訪問受限節(jié)點的前提下，只有節(jié)點 [0,5,6] 可以從節(jié)點 0 到達(dá)。

提示：

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 中的所有值 互不相同

🌟 求解思路&實現(xiàn)代碼&運行結(jié)果

---

? BFS

🥦 求解思路

1. 先將這棵無向樹建立起來，然后通過BFS來找到可以到達(dá)的最多節(jié)點的數(shù)目，在遍歷的過程，如果遇到restricted數(shù)組中限制的節(jié)點，直接跳過，否則，直接加入，計數(shù)加1，同時不要忘記將當(dāng)前節(jié)點標(biāo)記為走過的狀態(tài)，繼續(xù)該過程。
2. 有了基本的思路，接下來我們就來通過代碼來實現(xiàn)一下。

🥦 實現(xiàn)代碼

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;}
}

🥦 運行結(jié)果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！