一、題目

1、題目描述

現有一棵由?n?個節點組成的無向樹，節點編號從?0?到?n - 1?，共有?n - 1?條邊。

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

在不訪問受限節點的前提下，返回你可以從節點?0?到達的?最多?節點數目。

注意，節點?0?不?會標記為受限節點。

2、接口描述

?

class Solution {
public:int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {}
};

3、原題鏈接

2368. 受限條件下可到達節點的數目

---

二、解題報告

1、思路分析

先存圖，然后標記限制節點

然后從根開始往下深搜即可，對于父節點和標記節點不進行訪問

2、復雜度

時間復雜度： O(n)空間復雜度：O(n)

3、代碼詳解

?

class Solution {
public:
bool vis[100005];int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {memset(vis, 0, sizeof vis);vector<vector<int>> g(n);for(auto x : restricted) vis[x] = 1;for(auto& e : edges) g[e[0]].emplace_back(e[1]), g[e[1]].emplace_back(e[0]);function<int(int, int)> dfs = [&](int x, int fa)->int{int res = 1;for(auto y : g[x]) if(!vis[y] && y != fa) res += dfs(y, x);return res;};return dfs(0, -1);}
};