Teaching Kids Programming – Reachable Nodes With Restrictions (Graph Theory, Union Find, Disjoint Set, 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, Union Find, Disjoint Set, Undirected/Unweighted Graph)

Apart from DFS and BFS, we can also solve this Graph problem by using the Union Find Algorithm that is based on the Disjoint Set data structure.

We merge two vertices (to mark them as a same group) if both vertices of a given edge are not forbidden. Then we count how many nodes/vertices are in the same group as Node 0 (starting point).

The following is a Standard Python implementation of the Union Find algorithm + Disjoint Set Data Structure. The count method counts the number of the nodes that are in the same group as the given node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class UnionFind:
    def __init__(self, n):
        self.f = list(range(n))
        self.rank = [1] * n
        self.n = n
        self.size = n
 
    def merge(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] <= self.rank[ry]:
            rx, ry = ry, rx
        self.f[ry] = rx
        self.rank[rx] += 1
        self.size -= 1
        return True
 
    def find(self, x):
        if x != self.f[x]:
            self.f[x] = self.find(self.f[x])
        return self.f[x]
 
    def count(self, x):
        return sum(self.f[i] == self.f[x] for i in range(self.n))

class UnionFind:
    def __init__(self, n):
        self.f = list(range(n))
        self.rank = [1] * n
        self.n = n
        self.size = n

    def merge(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] <= self.rank[ry]:
            rx, ry = ry, rx
        self.f[ry] = rx
        self.rank[rx] += 1
        self.size -= 1
        return True

    def find(self, x):
        if x != self.f[x]:
            self.f[x] = self.find(self.f[x])
        return self.f[x]

    def count(self, x):
        return sum(self.f[i] == self.f[x] for i in range(self.n))

With the above, we can iterate over the edges and merge two vertices if neither is forbidden. The implementation is simpler and we don’t need to build the Graph, and using the Hash Set to remember the nodes whilst we traverse the undirected/unweighted graph.

1
2
3
4
5
6
7
8
9

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        blacklist = set(restricted)
        uf = UnionFind(n)
        for a, b in edges:
            if (a in blacklist) or (b in blacklist):
                continue
            uf.merge(a, b)
        return uf.count(0)

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        blacklist = set(restricted)
        uf = UnionFind(n)
        for a, b in edges:
            if (a in blacklist) or (b in blacklist):
                continue
            uf.merge(a, b)
        return uf.count(0)

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