Teaching Kids Programming – Reachable Nodes With Restrictions (Graph Theory, Recursive Depth First Search Algorithm, Undirected/Unweighted Graph)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Undirected Unweighted Graph Traversal Algorithms with Restriction

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.

Constraints:
2 <= n <= 10^5
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.

Hints:
Can we find all the reachable nodes in a single traversal?
Hint 2
Traverse the graph from node 0 while avoiding the nodes in restricted and do not revisit nodes that have been visited.
Hint 3
Keep count of how many nodes are visited in total.

Reachable Nodes With Restrictions (Graph Theory, Depth First Search Algorithm)

We need to first build the Graph from the given list of edges. And we can build the Graph to Adjacency List (another Data structure to store a Graph is Adjacency Matrix).

Since this is a undirected and unweighted Graph, we can traverse the Graph using the Depth First Search Algorithm. This can be done via Recursion or an iterative approach of using Stack.

We also need a hash set to remember to the nodes that we have seen so that we don’t re-visit them. If we have seen a node or the node is forbidden, then we simply return zero, otherwise, we keep walking to the neighbour nodes and increment the answer by one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:        
        B = set(restricted)
        G = defaultdict(list)
        for a, b in edges:
            G[a].append(b)
            G[b].append(a)
        seen = set()
 
        def dfs(i):
            if i in seen or i in B:
                return 0
            seen.add(i)
            ans = 1
            for x in G[i]:
                ans += dfs(x)
            return ans
 
        return dfs(0)

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:        
        B = set(restricted)
        G = defaultdict(list)
        for a, b in edges:
            G[a].append(b)
            G[b].append(a)
        seen = set()

        def dfs(i):
            if i in seen or i in B:
                return 0
            seen.add(i)
            ans = 1
            for x in G[i]:
                ans += dfs(x)
            return ans

        return dfs(0)

The time complexity is O(V+E) and the space complexity is O(N), here N=V, the vertices of the Graph.

Reachable Nodes With Restrictions (Graph Theory)

• Teaching Kids Programming - Reachable Nodes With Restrictions (Graph Theory, Iterative Depth First Search Algorithm, Undirected/Unweighted Graph)
• Teaching Kids Programming - Reachable Nodes With Restrictions (Graph Theory, Union Find, Disjoint Set, Undirected/Unweighted Graph)
• Teaching Kids Programming - Reachable Nodes With Restrictions (Graph Theory, Recursive Depth First Search Algorithm)
• Teaching Kids Programming - Reachable Nodes With Restrictions (Graph Theory, Breadth First Search Algorithm, Undirected/Unweighted Graph)

–EOF (The Ultimate Computing & Technology Blog) —