#1971

Find if Path Exists in Graph

pupil · 410 · lc easy +25 · verified · 54.8% accepted · 4,293 likes · top 48%

⚑ DFS / BFS: Connected Components & Reachability

Description

An undirected graph has n vertices labeled 0 to n - 1. Its edges are given in the 2D integer array edges, with edges[i] = [ui, vi] indicating a bidirectional connection between ui and vi. No two vertices share more than one edge, and no self-loops exist.

Given integers source and destination, return true if a path between them exists, 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.

Code

1

2

3

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: