LeetCode 1971: Find if Path Exists in Graph ·

Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2026-04-08 Source: Day 2 learning note

Study Context
#

This article is rebuilt from the exact LeetCode section in the learning note. I kept the note’s repair points, comparison points, and common mistakes, while removing unrelated non-LeetCode material from the same day.

Learning Note Extract
#

LC 1971 — Find if Path Exists in Graph
#

Pattern: BFS/DFS OR Union-Find
Critical: This is an undirected graph — add both directions when building adjacency list
BFS approach: Standard BFS from source. Return true if destination is reached.
Union-Find approach: Group all connected nodes. Return find(source) == find(destination)
Common bugs:
1. Building directed adjacency list for undirected graph
2. Applying Kahn’s in-degree logic to undirected graph — in-degree is meaningless here
3. Never calling union on edges — nodes stay in separate components
4. Calling union(x, y) with raw nodes instead of roots union(find(x), find(y))
5. Wrong rank increment — only increment when two trees of equal rank merge
Union-Find template:

parent = [i for i in range(n)]
rank = [0] * n

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return
    if rank[rx] > rank[ry]:
        parent[ry] = rx
    elif rank[rx] < rank[ry]:
        parent[rx] = ry
    else:
        parent[rx] = ry
        rank[ry] += 1

Trade-off: BFS = simpler, good for single query. Union-Find = better for multiple path queries on same graph (near O(1) per query after O(V+E) build).

Clean Solution
#

The note above captures the reasoning and the mistakes to avoid. The implementation below is the version I would submit.

from typing import List

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        parent = list(range(n))
        rank = [0] * n

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra == rb:
                return
            if rank[ra] < rank[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            if rank[ra] == rank[rb]:
                rank[ra] += 1

        for a, b in edges:
            union(a, b)

        return find(source) == find(destination)

Complexity
#

Time O((n+e) alpha(n)), Space O(n).

Mistakes To Watch
#

Treating the graph as directed.
Forgetting path compression / union is enough for connectivity.

Final Interview Explanation
#

Start from the state definition, then explain why the transition preserves that state. If there is a loop direction, state compression, or a similar-looking problem with a different answer shape, call that out explicitly because that is where this problem family usually breaks down.