LeetCode：2368. 受限条件下可到达节点的数目（dfs Java）

2368. 受限条件下可到达节点的数目

题目描述：

实现代码与解析：

DFS

原理思路：

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

实现代码与解析：

DFS

class Solution {
    public final int N = (int)2e5 + 10;

    // 邻接表
    int[] h = new int[N], e = new int[N * 2], ne = new int[N * 2];
    int idx;

    // 连边方法
    public void add(int a, int b) {
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    } 

    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        
        Arrays.fill(h, -1); // 别忘了
        // 构成邻接表
        for (int[] e: edges) {
            int a = e[0];
            int b = e[1];
            add(a, b);
            add(b, a);
        }

        // set记录被标记的节点
        Set<Integer> set = new HashSet<>();
        
        for (int t: restricted) {
            set.add(t);
        }

        // 从0节点dfs遍历
        int res = dfs(0, -1, set);
        return res;
    }

    public int dfs(int cur, int f, Set<Integer> set) {
        
        int count = 0;
        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j != f && !set.contains(j)) {
                count += dfs(j, cur, set);
            }
        }
        count++;
        return count;
    }
}