EasyNo. 1971
Find if Path Exists in Graph — LeetCode 1971 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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:
Python solution
class Solution:
def validPath(
self, n: int, edges: List[List[int]], source: int, destination: int
) -> bool:
def dfs(i: int) -> bool:
if i == destination:
return True
vis.add(i)
for j in g[i]:
if j not in vis and dfs(j):
return True
return False
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
vis = set()
return dfs(source)Complexity
- Time
- O(n + m)
- Space · auxiliary
- O(n + m)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1971. Find if Path Exists in Graph is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
| 0886 | Possible Bipartition | Medium |
Frequently asked questions
- How hard is LeetCode 1971. Find if Path Exists in Graph?
LeetCode 1971. Find if Path Exists in Graph is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1971. Find if Path Exists in Graph?
The Python solution on this page runs in O(n + m).
- What is the space complexity of LeetCode 1971. Find if Path Exists in Graph?
The Python solution on this page uses O(n + m) auxiliary space.
- What topics does LeetCode 1971. Find if Path Exists in Graph cover?
LeetCode 1971. Find if Path Exists in Graph is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.