# Reachable Nodes With Restrictions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reachable-nodes-with-restrictions)
Canonical: https://scaleengineer.com/dsa/problems/reachable-nodes-with-restrictions
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, Tree, Graph
**Companies:** [MakeMyTrip](https://scaleengineer.com/companies/makemytrip)
---
## Problem
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:**

![](https://assets.glich.co/dsa/reachable-nodes-with-restrictions/image0.png) 

**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:**

![](https://assets.glich.co/dsa/reachable-nodes-with-restrictions/image1.png) 

**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.

**Constraints:**

* `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**.

# Approaches
## Graph Traversal with Linear Search for Restrictions
This approach involves building a graph representation of the tree and then performing a standard graph traversal (like Breadth-First Search or Depth-First Search) starting from node 0. The key inefficiency in this method is how we check if a node is restricted. For every node we consider visiting, we perform a linear scan through the entire `restricted` array to see if it's present. While simple to implement, this repeated linear search leads to a high time complexity, making it unsuitable for large inputs.
**Time:** O(N * R), where `N` is the number of nodes and `R` is the length of the `restricted` array. Building the adjacency list takes `O(N)`. The BFS traversal visits each node at most once. For each node, we iterate its neighbors. The total number of edges considered is `2 * (N-1)`. For each potential new node to visit, we perform a linear scan of the `restricted` array, which takes `O(R)`. This results in a total time complexity dominated by `O(N * R)`. · **Space:** O(N). We need O(N) space for the adjacency list, O(N) for the `visited` array, and O(N) for the queue in the worst case (a star graph or line graph). This sums to O(N).
**Pros:** Conceptually simple, directly translating the problem statement.; Doesn't require complex data structures beyond a list and a queue.
**Cons:** Very inefficient due to the repeated linear scan of the `restricted` array.; Will result in a "Time Limit Exceeded" (TLE) error for the given constraints.
### Explanation
First, we construct an adjacency list from the input `edges` array. This allows us to easily find the neighbors of any given node. We then initialize a queue for BFS, a `visited` array to track visited nodes, and a counter for reachable nodes. We start by adding node 0 to the queue and marking it as visited.

We then enter a loop that continues as long as the queue is not empty. In each iteration, we dequeue a node. For each neighbor of the dequeued node, we first check if it has been visited. If not, we then check if it is a restricted node. This check is done by iterating through the `restricted` array. If the neighbor is not visited and not restricted, we mark it as visited, enqueue it, and increment our counter of reachable nodes. The process continues until the queue is empty, at which point the counter holds the total number of nodes reachable from node 0.

```java
import java.util.*;

class Solution {
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        // Step 1: Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // Step 2: Initialize for BFS
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        int count = 0;

        // Node 0 is not restricted, start from here
        queue.offer(0);
        visited[0] = true;
        count++;

        // Step 3: Perform BFS
        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v : adj.get(u)) {
                // Check if neighbor is visited
                if (!visited[v]) {
                    // Step 4: Linearly scan restricted array
                    boolean isRestricted = false;
                    for (int r : restricted) {
                        if (v == r) {
                            isRestricted = true;
                            break;
                        }
                    }
                    
                    if (!isRestricted) {
                        visited[v] = true;
                        queue.offer(v);
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Build an adjacency list representation of the tree from the `edges` array.
- Initialize a queue for Breadth-First Search (BFS) and add node `0`.
- Initialize a `visited` boolean array of size `n` and mark `visited[0]` as true.
- Initialize a counter `reachableCount` to 1.
- While the queue is not empty:
  - Dequeue a node `u`.
  - For each neighbor `v` of `u`:
    - If `v` has not been visited:
      - Linearly search for `v` in the `restricted` array.
      - If `v` is not found in `restricted`:
        - Mark `v` as visited.
        - Enqueue `v`.
        - Increment `reachableCount`.
- Return `reachableCount`.

## Optimized Traversal using DFS and a Hash Set
This approach significantly improves upon the previous one by optimizing the check for restricted nodes. Instead of a linear scan, we first store all restricted nodes in a `HashSet`. This allows for an average time complexity of O(1) for checking if a node is restricted. We then perform a Depth-First Search (DFS) starting from node 0. The recursive nature of DFS naturally explores the graph, and at each step, we use the hash set to quickly decide if we can proceed to a neighbor.
**Time:** O(N + R), where `N` is the number of nodes and `R` is the number of restricted nodes. Building the adjacency list takes `O(N)`. Populating the hash set takes `O(R)`. The DFS traversal visits each reachable node and edge once, which takes `O(N)` time in the worst case. Thus, the total time complexity is `O(N + R)`. · **Space:** O(N + R). `O(N)` for the adjacency list, `O(N)` for the `visited` array, `O(R)` for the restricted set, and `O(N)` for the recursion stack in the worst case (a skewed tree). This simplifies to `O(N + R)`.
**Pros:** Highly efficient and optimal for the given constraints.; The use of a hash set for restricted nodes is a key optimization.
**Cons:** The recursive implementation might lead to a `StackOverflowError` for very deep trees, which is a possibility with N up to 10^5.
### Explanation
The first step is to process the `restricted` array into a `HashSet` for efficient lookups. This takes time proportional to the number of restricted nodes. Next, we build the adjacency list representation of the tree, just as in the previous approach. We also need a `visited` array to prevent re-visiting nodes.

We then initiate a recursive DFS function, starting with `dfs(0)`. This function will return the count of reachable nodes in the component connected to the current node.

The `dfs` function works as follows:
1. First, it checks if the current node is restricted. If so, it cannot be part of the reachable set, so we return 0.
2. Mark the current node as visited.
3. Initialize a local count to 1 (for the current node itself).
4. Iterate through all neighbors of the current node.
5. For each neighbor, if it has not been visited, recursively call `dfs` on that neighbor and add the returned count to the local count.
6. Return the total local count.

The initial call to `dfs(0)` will give the final answer.

```java
import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private Set<Integer> restrictedSet;
    private boolean[] visited;
    
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        // Step 1: Build adjacency list
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // Step 2: Store restricted nodes in a HashSet for O(1) lookups
        restrictedSet = new HashSet<>();
        for (int node : restricted) {
            restrictedSet.add(node);
        }

        // Step 3: Initialize visited array and start DFS
        visited = new boolean[n];
        return dfs(0);
    }

    private int dfs(int u) {
        // A node is not reachable if it's restricted
        if (restrictedSet.contains(u)) {
            return 0;
        }
        
        visited[u] = true;
        int count = 1; // Count the current node

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                count += dfs(v);
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a `HashSet` from the `restricted` array for O(1) average time lookups.
- Build an adjacency list for the tree.
- Initialize a `visited` boolean array of size `n`.
- Define a recursive DFS function `dfs(node)`:
  - If `node` is in the restricted set, return 0.
  - Mark `node` as visited.
  - Initialize `count = 1` (for the current node).
  - For each neighbor `v` of `node`:
    - If `v` is not visited:
      - Add the result of `dfs(v)` to `count`.
  - Return `count`.
- Call `dfs(0)` to start the traversal and get the result.

## Optimized Traversal using BFS and a Hash Set
This approach is an iterative alternative to the recursive DFS, using Breadth-First Search (BFS). It shares the same core optimization of using a `HashSet` for O(1) checks of restricted nodes. BFS explores the graph level by level, which can be advantageous in some scenarios, such as finding the shortest path. For this problem, its performance is equivalent to DFS. It uses a queue to manage the nodes to visit, avoiding deep recursion and the potential for stack overflow errors.
**Time:** O(N + R). `O(N)` for building the adjacency list, `O(R)` for the hash set, and `O(N)` for the BFS traversal. Each reachable node and edge is processed once. · **Space:** O(N + R). `O(N)` for the adjacency list, `O(N)` for the `visited` array, `O(R)` for the restricted set, and `O(N)` for the queue in the worst case.
**Pros:** Optimal time and space complexity.; Iterative approach avoids potential `StackOverflowError` that can occur with deep recursion in DFS.; Generally considered safer for very large graphs compared to recursive DFS.
**Cons:** The code can be slightly more verbose than a recursive DFS implementation.
### Explanation
Similar to the DFS approach, we begin by building the adjacency list and populating a `HashSet` with the restricted nodes. We then initialize a queue and add the starting node, `0`. We also use a `visited` array to keep track of nodes already added to the queue to avoid redundant processing. We initialize a counter for reachable nodes to 1, since we start at node 0.

The main part of the algorithm is a loop that runs as long as the queue is not empty. Inside the loop:
1. We dequeue a node `u`.
2. We iterate through all its neighbors `v`.
3. For each neighbor `v`, we check if it has been visited and if it is in the `restrictedSet`.
4. If `v` is unvisited and not restricted, we mark it as visited, increment our reachable node counter, and enqueue `v` for future processing.

After the loop terminates (meaning we have explored all reachable, non-restricted nodes), the counter will hold the final answer.

```java
import java.util.*;

class Solution {
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        // Step 1: Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // Step 2: Store restricted nodes in a HashSet for O(1) lookups
        Set<Integer> restrictedSet = new HashSet<>();
        for (int node : restricted) {
            restrictedSet.add(node);
        }

        // Step 3: Initialize for BFS
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        int count = 0;

        // Start from node 0, which is guaranteed not to be restricted
        queue.offer(0);
        visited[0] = true;
        count = 1;

        // Step 4: Perform BFS
        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v : adj.get(u)) {
                if (!visited[v] && !restrictedSet.contains(v)) {
                    visited[v] = true;
                    count++;
                    queue.offer(v);
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a `HashSet` from the `restricted` array.
- Build an adjacency list for the tree.
- Initialize a queue and add node `0`.
- Initialize a `visited` boolean array and mark `visited[0]` as true.
- Initialize `reachableCount = 1`.
- While the queue is not empty:
  - Dequeue a node `u`.
  - For each neighbor `v` of `u`:
    - If `v` is not visited and not in the restricted set:
      - Mark `v` as visited.
      - Enqueue `v`.
      - Increment `reachableCount`.
- Return `reachableCount`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  boolean[] vis;
private
  int ans;
public
  int reachableNodes(int n, int[][] edges, int[] restricted) {
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    vis = new boolean[n];
    for (int v : restricted) {
      vis[v] = true;
    }
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    ans = 0;
    dfs(0);
    return ans;
  }
private
  void dfs(int u) {
    if (vis[u]) {
      return;
    }
    ++ans;
    vis[u] = true;
    for (int v : g[u]) {
      dfs(v);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int ans;
  int reachableNodes(int n, vector<vector<int>> &edges,
                     vector<int> &restricted) {
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    vector<bool> vis(n);
    for (int v : restricted)
      vis[v] = true;
    ans = 0;
    dfs(0, g, vis);
    return ans;
  }
  void dfs(int u, vector<vector<int>> &g, vector<bool> &vis) {
    if (vis[u])
      return;
    vis[u] = true;
    ++ans;
    for (int v : g[u])
      dfs(v, g, vis);
  }
};

```

### Python

```python
class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int: g = defaultdict(list) vis = [False] * n for v in restricted: vis[v] = True for a, b in edges: g[a]. append(b) g[b]. append(a) def dfs(u): nonlocal ans if vis[u]: return ans += 1 vis[u] = True for v in g[u]: dfs(v) ans = 0 dfs(0) return ans

```