2368. Reachable Nodes With Restrictions LeetCode Solution
In this guide, you will get 2368. Reachable Nodes With Restrictions LeetCode Solution with the best time and space complexity. The solution to Reachable Nodes With Restrictions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Reachable Nodes With Restrictions
There is an undirected tree with n nodes labeled from 0 to n – 1 and n – 1 edges.
You are given a 2D integer array edges of length n – 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which represents restricted nodes.
Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.
Note that node 0 will not be a restricted node.
Example 1:
Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
Output: 4
Explanation: The diagram above shows the tree.
We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.
Example 2:
Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
Output: 3
Explanation: The diagram above shows the tree.
We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.
2 <= n <= 105
edges.length == n – 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.
1 <= restricted.length < n
1 <= restricted[i] < n
All the values of restricted are unique.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2368. Reachable Nodes With Restrictions LeetCode Solution in C++
class Solution {
public:
int reachableNodes(int n, vector<vector<int>>& edges,
vector<int>& restricted) {
vector<vector<int>> tree(n);
vector<bool> seen(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
for (const int r : restricted)
seen[r] = true;
return dfs(tree, 0, seen);
}
private:
int dfs(const vector<vector<int>>& tree, int u, vector<bool>& seen) {
if (seen[u])
return 0;
seen[u] = true;
int ans = 1;
for (const int v : tree[u])
ans += dfs(tree, v, seen);
return ans;
}
}; /* code provided by PROGIEZ */
2368. Reachable Nodes With Restrictions LeetCode Solution in Java
class Solution {
public int reachableNodes(int n, int[][] edges, int[] restricted) {
List<Integer>[] tree = new List[n];
boolean[] seen = new boolean[n];
for (int i = 0; i < n; ++i)
tree[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
tree[u].add(v);
tree[v].add(u);
}
for (final int r : restricted)
seen[r] = true;
return dfs(tree, 0, seen);
}
private int dfs(List<Integer>[] tree, int u, boolean[] seen) {
if (seen[u])
return 0;
seen[u] = true;
int ans = 1;
for (final int v : tree[u])
ans += dfs(tree, v, seen);
return ans;
}
} // code provided by PROGIEZ
2368. Reachable Nodes With Restrictions LeetCode Solution in Python
class Solution:
def reachableNodes(
self,
n: int,
edges: list[list[int]],
restricted: list[int],
) -> int:
tree = [[] for _ in range(n)]
seen = set(restricted)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
def dfs(u: int) -> int:
if u in seen:
return 0
seen.add(u)
return 1 + sum(dfs(v) for v in tree[u])
return dfs(0) # code by PROGIEZ
