2368. Reachable Nodes With Restrictions


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.

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:

  1. Constructing an adjacency list from the edges array, allowing us to access all connected nodes from a given node easily.
  2. 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.
  3. 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:

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

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

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

  4. 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.
  5. 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.

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

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

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

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:

1    0
2   / \
3  1   2
4 / \
53   4

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

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

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

    1g = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}
  2. Pre-Marking Restricted Nodes: We then create a list vis initialized with False values. Since only node 3 is restricted, vis will be:

    1vis = [False, False, False, True, False]

    Node 3 is marked True to indicate it's visited/restricted.

  3. Graph Construction: Our graph g has already been constructed from the edges array in step 1.

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

    1def dfs(u):
    2    if vis[u]:
    3        return 0
    4    vis[u] = True
    5    count = 1
    6    for neigh in g[u]:
    7        count += dfs(neigh)
    8    return count

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

  5. Initialization and Invocation: With ans = 0, we call dfs(0) and begin the DFS traversal.

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


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄