2368. Reachable Nodes With Restrictions

MediumTreeDepth-First SearchBreadth-First SearchGraphArrayHash Table

Problem Description

In this problem, we are given an undirected tree with n nodes, where each node is labeled from 0 to n - 1. A 2D integer array edges is provided that contains n - 1 pairs of integers, with each pair [ai, bi] indicating an edge between the nodes ai and bi. Alongside this, we have an integer array restricted that lists restricted nodes which should not be visited.

Our goal is to find the maximum number of nodes that can be reached from node 0 without visiting any of the restricted nodes. It's important to note that node 0 is not a restricted node.

The result should be the count of accessible nodes, including node 0, keeping in mind the restricted nodes' constraint.

Flowchart Walkthrough

To analyze the approach for LeetCode problem 2368: Reachable Nodes With Restrictions using the Flowchart, let's follow this process:

Is it a graph?

Yes: The problem represents connections between nodes explicitly, with certain nodes having restrictions on connectivity, effectively forming a graph scenario.

Is it a tree?

Yes: Despite the restrictions, the graph is still essentially a tree because it starts from a root node (1) and explores other nodes without cycles, adhering to tree properties.

Is the problem related to directed acyclic graphs (DAGs)?

No: We are dealing with a tree here, which by definition is acyclic but undirected, and our focus is not on directed acyclic structures.

Is the problem related to shortest paths?

No: The task is about counting the number of reachable nodes, not finding the shortest path to any node.

Does the problem involve connectivity?

Yes: The goal is to verify the reachability of nodes given certain restrictions, highlighting the problem as a connectivity issue.

Is the graph weighted?

No: The connections between nodes are either existent or restricted; there’s no weight like cost or distance associated with the edges.

Conclusion: Given that it's an unweighted connectivity problem in a tree-like structure, the flowchart leads us to employ a DFS (Depth-First Search) to explore maximum nodes while respecting the restrictions. DFS is typically efficient for tree structures to visit each node and check conditions or applications like reachability.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we use depth-first search (DFS), which is a standard graph traversal algorithm, to explore the graph starting from node 0. The graph is represented using an adjacency list, which is a common way to represent graphs in memory.

The key steps involve:

Constructing an adjacency list from the edges array, allowing us to access all connected nodes from a given node easily.
Creating a visited array, vis, to keep track of both visited and restricted nodes, marking restricted nodes as visited preemptively so that we don't traverse them during DFS.
Implementing a recursive DFS function that will traverse the graph. For each node u that is not visited and not restricted, the function will:
- Increase the count of reachable nodes, ans, by 1.
- Mark the node as visited.
- Recursively call DFS for all adjacent nodes of u.

When the DFS function completes, ans will contain the total count of reachable nodes from node 0, ensuring that no restricted nodes are counted. This approach guarantees that we explore all possible paths in a depth-first manner while skipping over the restricted nodes and only counting the valid ones.

Learn more about Tree, Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution utilizes the Depth-First Search (DFS) algorithm to traverse the tree from node 0 and count the maximum number of reachable nodes without visiting any restricted nodes. Here's how the implementation works:

Data Structure: We use a defaultdict to create an adjacency list g that represents the graph. Each key in this dictionary corresponds to a node, and the value is a list of nodes that are connected to it by an edge. This allows us to efficiently access all neighbor nodes of any given node.
Pre-Marking Restricted Nodes: We create a list vis of boolean values to keep track of whether a node has been visited or is restricted. Its length is n to cover all nodes. Restricted nodes are preemptively marked as visited (i.e., True) since we don't want to include them in our count.
Graph Construction: For each edge provided in the edges array, we add the corresponding nodes to the adjacency list of each other. Since the graph represents an undirected tree, if there is an edge between a and b, then b needs to be in the adjacency list of a and vice versa.
DFS (Depth-First Search) Function: We define a recursive function dfs that takes a node u as an argument. Within this function, we check if u is already visited or not. If it hasn't been visited:
- We increment the reachable nodes count ans by 1.
- We mark u as visited by setting vis[u] to True.
- We then call dfs recursively for all the unvisited neighbor nodes of u found in the adjacency list g[u]. The use of recursion inherently follows a depth-first traversal, going as deep as possible along one branch before backtracking.
Initialization and Invocation: Before invoking the DFS function, we initialize the ans variable to 0, which will be used to keep track of the number of reachable nodes. We then call dfs(0) to start the traversal from node 0.
Result: After the DFS completes, ans gives us the total number of nodes that can be reached from node 0 without traversing any restricted nodes, and this value is returned.

In this way, the DFS algorithm, an efficient graph traversal technique, along with an adjacency list representation of the tree, allows us to solve the problem with a concise and effective approach.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let’s take a small example to illustrate the solution approach described above.

Suppose we have 5 nodes (from 0 to 4) and n - 1 edges connecting them as follows: edges = [[0, 1], [0, 2], [1, 3], [1, 4]]. The restricted list containing the nodes that cannot be visited is restricted = [3].

Based on the edges, the tree structure looks like this:

Here, node 3 is restricted and should not be visited.

Now, let’s walk through the steps of the solution approach:

Data Structure: We use a defaultdict(list) to construct the adjacency list g representing the graph:

g = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}

Pre-Marking Restricted Nodes: We then create a list vis initialized with False values. Since only node 3 is restricted, vis will be:
```
vis = [False, False, False, True, False]
```
Node 3 is marked True to indicate it's visited/restricted.
Graph Construction: Our graph g has already been constructed from the edges array in step 1.

DFS (Depth-First Search) Function: We write a recursive function dfs(u) that:

def dfs(u):
    if vis[u]:
        return 0
    vis[u] = True
    count = 1
    for neigh in g[u]:
        count += dfs(neigh)
    return count

This function will count reachable nodes not previously counted nor restricted.

Initialization and Invocation: With ans = 0, we call dfs(0) and begin the DFS traversal.
Result: We visit node 0, which isn't in the restricted list nor visited. So ans is now 1. The dfs goes on to visit nodes 1 and 2. Node 1 has two children, 3 and 4, but since 3 is restricted, it only counts 4. After the complete DFS call, the ans value is 4 (nodes 0, 1, 2, and 4).

In this example, the ans value after running the DFS algorithm implies we can reach 4 nodes from node 0 without visiting any restricted nodes. This is consistent with our tree structure, taking into account the restrictions.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
5        # Create a graph represented as an adjacency list
6        graph = defaultdict(list)
7        # A list to keep track of visited nodes, default to False
8        visited = [False] * n
9      
10        # Mark restricted nodes as visited so they won't be traversed
11        for node in restricted:
12            visited[node] = True
13      
14        # Construct the graph by adding edges
15        for start, end in edges:
16            graph[start].append(end)
17            graph[end].append(start)
18
19        # Depth-First Search (DFS) function to traverse the graph
20        def dfs(node):
21            nonlocal count_visited
22            # If the node is already visited or restricted, return
23            if visited[node]:
24                return
25          
26            # Increase the count of visited (reachable) nodes
27            count_visited += 1
28            # Mark the node as visited
29            visited[node] = True
30          
31            # Recursively visit all adjacent nodes
32            for adjacent in graph[node]:
33                dfs(adjacent)
34
35        # Initialize the count of reachable nodes
36        count_visited = 0
37        # Start DFS from the first node
38        dfs(0)
39        # Return the number of reachable nodes
40        return count_visited
41

1class Solution {
2    // Graph represented as an adjacency list
3    private List<Integer>[] graph;
4    // Array to keep track of visited nodes
5    private boolean[] visited;
6    // Counter to keep track of the number of reachable nodes
7    private int numberOfReachableNodes;
8
9    // Method to return the number of reachable nodes
10    public int reachableNodes(int n, int[][] edges, int[] restricted) {
11        // Initialize the graph for each node
12        graph = new List[n];
13        for (int i = 0; i < n; i++) {
14            graph[i] = new ArrayList<>();
15        }
16
17        // Mark restricted nodes as visited so they won't be explored in DFS
18        visited = new boolean[n];
19        for (int restrictedNode : restricted) {
20            visited[restrictedNode] = true;
21        }
22
23        // Build the graph by adding edges
24        for (int[] edge : edges) {
25            int from = edge[0], to = edge[1];
26            graph[from].add(to);
27            graph[to].add(from);
28        }
29
30        // Initialize the count of reachable nodes and start DFS from node 0
31        numberOfReachableNodes = 0;
32        dfs(0);
33
34        // Return the total count of reachable nodes
35        return numberOfReachableNodes;
36    }
37
38    // DFS method to traverse nodes
39    private void dfs(int node) {
40        // If the current node is visited/restricted, do not proceed with DFS
41        if (visited[node]) {
42            return;
43        }
44
45        // Mark the node as visited and increment the reachable nodes counter
46        numberOfReachableNodes++;
47        visited[node] = true;
48
49        // Visit all the neighbors of the current node
50        for (int neighbor : graph[node]) {
51            dfs(neighbor);
52        }
53    }
54}
55

1class Solution {
2public:
3    int nodeCount; // Use a more descriptive name for this variable, which represents the count of reachable nodes.
4
5    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
6        vector<vector<int>> graph(n); // Use 'graph' to store the adjacency list representation of the graph.
7        // Construct the graph from the given edge list.
8        for (const auto& edge : edges) {
9            int from = edge[0], to = edge[1];
10            graph[from].push_back(to);
11            graph[to].push_back(from);
12        }
13        vector<bool> visited(n, false); // Use 'visited' to mark the visited nodes, initialized to false.
14        // Mark the restricted nodes as visited so they won't be counted.
15        for (int node : restricted) visited[node] = true;
16      
17        // Initialize the reachable node count to zero before starting the DFS.
18        nodeCount = 0;
19        // Start depth-first search from node 0.
20        dfs(0, graph, visited);
21        return nodeCount; // Return the count of reachable nodes after the DFS is complete.
22    }
23
24    void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
25        if (visited[node]) {
26            // If the node has been visited or is restricted, return early.
27            return;
28        }
29        // Mark the current node as visited.
30        visited[node] = true;
31        // Increment the count of reachable nodes.
32        nodeCount++;
33        // Iterate over all the neighbors of the current node.
34        for (int neighbor : graph[node]) {
35            // Perform DFS on all non-visited neighbors.
36            dfs(neighbor, graph, visited);
37        }
38    }
39};
40

1function reachableNodes(n: number, edges: number[][], restricted: number[]): number {
2    let nodeCount = 0; // Holds the count of nodes that can be reached
3    const visited = new Array(n).fill(false); // Tracks visited nodes
4    const adjacencyList = new Map<number, number[]>(); // Adjacency list to represent the graph
5  
6    // Construct the adjacency list from the edges
7    for (const [start, end] of edges) {
8        // Append the end node to the adjacency list of the start node
9        adjacencyList.set(start, [...(adjacencyList.get(start) ?? []), end]);
10        // Append the start node to the adjacency list of the end node
11        adjacencyList.set(end, [...(adjacencyList.get(end) ?? []), start]);
12    }
13  
14    // Depth-First Search function to explore the graph
15    const dfs = (currentNode: number) => {
16        // If the node has been visited or is restricted, stop the search
17        if (restricted.includes(currentNode) || visited[currentNode]) {
18            return;
19        }
20        // Increment node count and mark the node as visited
21        nodeCount++;
22        visited[currentNode] = true;
23      
24        // Iterate over all adjacent nodes and explore them
25        for (const neighbor of adjacencyList.get(currentNode) ?? []) {
26            dfs(neighbor);
27        }
28    };
29  
30    // Begin the Depth-First Search from node 0
31    dfs(0);
32
33    // Return the total number of nodes that can be reached
34    return nodeCount;
35}
36

Time and Space Complexity

The given Python code defines a Solution class with a method reachableNodes to count the number of nodes in an undirected graph that can be reached without visiting any of the restricted nodes. It uses a Depth First Search (DFS) approach.

Time Complexity

The time complexity of the code is primarily determined by the DFS traversal of the graph provided by edges.

The adjacency list for the graph is constructed in linear time relative to the number of edges. for a, b in edges loop runs |E| times, where |E| is the number of edges.
The DFS (dfs function) visits each vertex only once, because once a vertex has been visited, it is marked as visited (vis[u] = True).
Each edge is traversed exactly twice in an undirected graph (once for each direction), during the entire DFS process.

Therefore, the time complexity of the DFS traversal is O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges.

Combining the adjacency list construction and the DFS traversal, the total time complexity remains O(|V| + |E|) since both are dependent on the size of the graph.

Space Complexity

The space complexity is determined by:

The storage of the graph in the adjacency list g, which consumes O(|V| + |E|) space.
The recursive DFS call stack, which, in the worst case, could hold all vertices if the graph is a linked list shape (each vertex connected to only one other), hence O(|V|) in space.
The vis array, which takes O(|V|) space, to keep track of visited nodes, including restricted ones.

Summing this up, the space complexity is O(|V| + |E|) when considering both the adjacency list and the DFS stack.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know