邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。
- 题目：6139. 受限条件下可到达节点的数目
现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。 给你一个二维整数数组 edges ，长度为 n - 1 ， 其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。 另给你一个整数数组 restricted 表示 受限 节点。 在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。 注意，节点 0 不 会标记为受限节点。
- 示例：
输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5] 输出：4 解释：上图所示正是这棵树。 在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。
- 将restricted中的点转化为vis数组的已访问状态，建图然后通过BFS从0开始遍历图，统计入队节点数即为答案。
- 示例中可以建立的邻接表如下：
[ [1,4,5], [0,2,3], [1], [1], [0], [0,6], [5] ]
- 实现：
class Solution { public int reachableNodes(int n, int[][] edges, int[] restricted) { // 邻接表的结构 List<Integer>[] adj = new List[n]; for (int i = 0; i < n; ++i){ adj[i] = new ArrayList<>(); } // 邻接表建图 for (int i = 0; i < n - 1; ++i){ adj[edges[i][0]].add(edges[i][1]); adj[edges[i][1]].add(edges[i][0]); } boolean[] vis = new boolean[n]; // 处理restricted数组 for (int num : restricted) vis[num] = true; Deque<Integer> q = new LinkedList<>(); q.addLast(0); vis[0] = true; int ans = 1; while (!q.isEmpty()){ // 尾部添加，头部读取，校验是否访问过 int cur = q.pollFirst(); for (int next : adj[cur]){ if (!vis[next]){ q.addLast(next); vis[next] = true; ++ans; } } } return ans; } }
参考链接：https://leetcode.cn/problems/reachable-nodes-with-restrictions/solution/by-darkbin-elga/
