We’re given an undirected graph with a source and destination node. We’re asked to determine if there exists a path between the two nodes in the graph. This is a classic connectivity problem, we can solve this by using Union-Find. For each edge, (x, y), we know each node is connected, so we execute union_set on the two nodes to reflect that. After processing all the edges, the Union-Find data structure will have all the nodes connected in their disjoint sets. If two nodes are both in the same disjoint set, then a path exists between. Therefore, if our source and destination nodes are in the same set, we return True - there is a path between them. Otherwise, we return False.
The solution is as follows:
from collections import defaultdict
class UnionFind:
def __init__(self, n: int) -> None:
self.parent, self.rank = [i for i in range(n)], [0 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]:
self.parent[xset] = yset
elif self.rank[yset] < self.rank[xset]:
self.parent[yset] = xset
else:
self.parent[yset] = xset
self.rank[xset] += 1
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
uf = UnionFind(n)
for x, y in edges:
uf.union_set(x, y)
return uf.find(source) == uf.find(destination)_ 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.