1971. Find if Path Exists in Graph
There is a bi-directional graph with n
vertices, where each vertex is labeled from 0
to n - 1
(inclusive). The edges in the graph are represented as a 2D integer array edges
, where each edges[i] = [ui, vi]
denotes a bi-directional edge between vertex ui
and vertex vi
. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
You want to determine if there is a valid path that exists from vertex source
to vertex destination
.
Given edges
and the integers n
, source
, and destination
, return true
if there is a valid path from source
to destination
, or false
otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2
Example 2:
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
Constraints:
1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
0 <= source, destination <= n - 1
- There are no duplicate edges.
- There are no self edges.
# class DSU:
# def __init__(self, n: int):
# self.root = [i for i in range(n)]
# def findRoot(self, target: int) -> int:
# while target != self.root[target]:
# target = self.root[target]
# return target
# def union(self, val1: int, val2: int) -> None:
# root1 = self.findRoot(val1)
# root2 = self.findRoot(val2)
# if root1 != root2:
# self.root[root2] = root1# class Solution:
# def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# # using disjoint sets
# init = DSU(n)
# # make union
# for vertex1, vertex2 in edges:
# init.union(vertex1, vertex2)
# src1 = init.findRoot(source)
# src2 = init.findRoot(destination)
# return True if src1 == src2 else False# class Solution:
# def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# # DFS recursive
# tempDict = collections.defaultdict(list)
# for vertex1, vertex2 in edges:
# tempDict[vertex1].append(vertex2)
# tempDict[vertex2].append(vertex1)
# visited = set()
# def dfs(node, target):
# if node == target:
# return True
# if node not in visited:
# visited.add(node)
# neighbors = tempDict[node]
# for i in neighbors:
# if dfs(i, target):
# return True
# return dfs(source, destination)class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# BFS iterative
tempDict = collections.defaultdict(list)
for vertex1, vertex2 in edges:
tempDict[vertex1].append(vertex2)
tempDict[vertex2].append(vertex1)
visited = set()
que = collections.deque([source])
while que:
node = que.popleft()
if node == destination:
return True
if node not in visited:
visited.add(node)
neighbours = tempDict[node]
for i in neighbours:
que.append(i)
return False