Practice/Microsoft/Leetcode 1971. Find if Path Exists in Graph

Leetcode 1971. Find if Path Exists in Graph

CodingMust

Problem

You are given an undirected graph represented by n nodes labeled from 0 to n - 1. The graph is provided as a list of edges where each edge is represented as [u, v], indicating a bidirectional connection between node u and node v.

Your task is to determine whether a valid path exists between a given source node and a destination node. Return true if such a path exists, otherwise return false.

Requirements

1. Implement a function that checks connectivity between two nodes in an undirected graph
2. The graph may contain cycles and multiple connected components
3. Handle the case where source and destination are the same node
4. Process the edge list to build an appropriate graph representation
5. Use an efficient traversal or disjoint-set algorithm

Constraints

• 1 <= n <= 200,000
• 0 <= edges.length <= 200,000
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi (no self-loops)
• 0 <= source, destination <= n - 1
• There are no duplicate edges
• The graph is undirected
• Time complexity should be O(n + m) where m is the number of edges
• Space complexity should be O(n + m)

Examples

Example 1:

` Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from node 0 to node 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: The graph has two separate connected components: \{0, 1, 2\} and \{3, 4, 5\}. There is no path connecting nodes in different components.

Example 3:

Input: n = 1, edges = [], source = 0, destination = 0 Output: true Explanation: The source and destination are the same node, which is always reachable from itself.