【LeetCode】受限条件下可到达节点的数目 Java 题解

作者：Albert

2022 年 8 月 08 日
本文字数：1108 字
阅读完需：约 4 分钟

题目描述

现有一棵由 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 到达。

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/reachable-nodes-with-restrictions著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是图处理题目。图题目的一般解法是 DFS。 DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。
分析题目，题目给出的是无向树，我们在创建树的时候，edges 是双向的，使用 edges 来构建树。
构建完成基本关系之后，需要处理受限节点。在代码实践中，我们可以直接将 restricted 的位置标记为访问过的节点，方便计算。
题目中明确指出了在不访问受限节点的前提下，返回你可以从节点 0 到达的最多节点数目。因此我们可以 DFS 直接从 0 开始访问。具体代码实现如下，供参考。

通过代码

class Solution {    List<Integer>[] g;    boolean[] vis;    int ans;        public int reachableNodes(int n, int[][] edges, int[] restricted) {        vis = new boolean[n];        for (int r : restricted ) {            vis[r] = true;        }                g = new ArrayList[n];        Arrays.setAll(g, e -> new ArrayList<>());        for (int[] e : edges) {            int x = e[0], y = e[1];            g[x].add(y);            g[y].add(x);        }                dfs(0);        return  ans;    }        private void dfs(int x) {        vis[x] = true;        ++ans;        for (int next : g[x]) {            if (!vis[next]) {                dfs(next);             }           }    }

}