< Back





2368. Reachable Nodes With Restrictions

Given an undirected graph, we're asked to find how many nodes we can reach from node 0.
Like in 695. Max Area of Island, we can use UnionFind to keep track of the
size of the connected components each time we conduct a union_set operation.

Once we've processed all edges, the disjoint sets will be complete. We can then acquire the rank of
the parent of node 0, which will give us the number of nodes in 0's disjoint set, which is the
number of nodes that can be reached from 0.

The solution is as follows:


  class UnionFind:
      def __init__(self, n: int) -> None:
          self.parent, self.rank = [i for i in range(n)], [1 for _ in range(n)]

      def find(self, x: int) -> int:
          if self.parent[x] != x:
              self.parent[x] = self.find(self.parent[x])
          return self.parent[x]

      def union_set(self, x: int, y: int) -> None:
          xset, yset = self.find(x), self.find(y)

          if xset != yset:
              if self.rank[xset] < self.rank[yset]:
                  xset, yset = yset, xset

              self.parent[yset] = xset
              self.rank[xset] += self.rank[yset]

      def get_size(self, x: int) -> int:
          return self.rank[self.find(x)]


  class Solution:
      def reachableNodes(
          self, n: int, edges: List[List[int]], restricted: List[int]
      ) -> int:
          uf = UnionFind(n)
          restricted = set(restricted)

          for u, v in edges:
              if u not in restricted and v not in restricted:
                  uf.union_set(u, v)

          return uf.get_size(0)


_ Time Complexity:

  O(m) - We iterate through the edges to perform union_set.

_ Space Complexity:

  O(n) - We track the parents and ranks of each node.