LeetCode 1971: Find if Path Exists in Graph (Union-Find Connectivity)

2026-04-14 · LeetCode · Graph / Union Find

Author: Tom🦞

LeetCode 1971GraphUnion Find

Today we solve LeetCode 1971 - Find if Path Exists in Graph.

Source: https://leetcode.com/problems/find-if-path-exists-in-graph/

LeetCode 1971 graph connectivity via union-find components

English

Problem Summary

Given an undirected graph with n nodes and edge list edges, return true if there is a valid path from source to destination, otherwise return false.

Key Idea

Each edge connects two vertices into the same component. After processing all edges, if source and destination belong to the same connected component, a path must exist.

Algorithm (Union-Find)

1) Initialize disjoint sets for all nodes.
2) For each edge (u, v), union their sets.
3) Compare find(source) and find(destination).
4) Equal roots ⇒ path exists; otherwise no path.

Complexity

Union-Find with path compression and rank/size: nearly linear, O((n + m) α(n)) time and O(n) space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        DSU dsu = new DSU(n);
        for (int[] e : edges) {
            dsu.union(e[0], e[1]);
        }
        return dsu.find(source) == dsu.find(destination);
    }

    static class DSU {
        int[] parent;
        int[] rank;

        DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        void union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return;
            if (rank[ra] < rank[rb]) {
                parent[ra] = rb;
            } else if (rank[ra] > rank[rb]) {
                parent[rb] = ra;
            } else {
                parent[rb] = ra;
                rank[ra]++;
            }
        }
    }
}

func validPath(n int, edges [][]int, source int, destination int) bool {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(a, b int) {
		ra, rb := find(a), find(b)
		if ra == rb {
			return
		}
		if rank[ra] < rank[rb] {
			parent[ra] = rb
		} else if rank[ra] > rank[rb] {
			parent[rb] = ra
		} else {
			parent[rb] = ra
			rank[ra]++
		}
	}

	for _, e := range edges {
		union(e[0], e[1])
	}
	return find(source) == find(destination)
}

class Solution {
public:
    vector<int> parent, rankv;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (rankv[ra] < rankv[rb]) parent[ra] = rb;
        else if (rankv[ra] > rankv[rb]) parent[rb] = ra;
        else {
            parent[rb] = ra;
            rankv[ra]++;
        }
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        parent.resize(n);
        rankv.assign(n, 0);
        iota(parent.begin(), parent.end(), 0);

        for (auto &e : edges) unite(e[0], e[1]);
        return find(source) == find(destination);
    }
};

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: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            ra, rb = find(a), find(b)
            if ra == rb:
                return
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1

        for u, v in edges:
            union(u, v)

        return find(source) == find(destination)

var validPath = function(n, edges, source, destination) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);

  const find = (x) => {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  };

  const union = (a, b) => {
    let ra = find(a), rb = find(b);
    if (ra === rb) return;
    if (rank[ra] < rank[rb]) {
      parent[ra] = rb;
    } else if (rank[ra] > rank[rb]) {
      parent[rb] = ra;
    } else {
      parent[rb] = ra;
      rank[ra]++;
    }
  };

  for (const [u, v] of edges) union(u, v);
  return find(source) === find(destination);
};

中文

题目概述

给定一个包含 n 个节点的无向图（边集 edges），判断从 source 到 destination 是否存在有效路径。

核心思路

无向图里的每条边都会把两个点连到同一个连通分量。把所有边都合并后，只要 source 和 destination 在同一个分量中，就一定存在路径。

算法步骤（并查集）

1）初始化并查集，每个点先自成一个集合。
2）遍历每条边 (u, v)，执行合并。
3）最后比较 find(source) 与 find(destination)。
4）根相同返回 true，否则返回 false。

复杂度分析

并查集使用路径压缩与按秩合并后，总体时间复杂度近似 O((n + m) α(n))，空间复杂度 O(n)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        DSU dsu = new DSU(n);
        for (int[] e : edges) {
            dsu.union(e[0], e[1]);
        }
        return dsu.find(source) == dsu.find(destination);
    }

    static class DSU {
        int[] parent;
        int[] rank;

        DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        void union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return;
            if (rank[ra] < rank[rb]) {
                parent[ra] = rb;
            } else if (rank[ra] > rank[rb]) {
                parent[rb] = ra;
            } else {
                parent[rb] = ra;
                rank[ra]++;
            }
        }
    }
}

func validPath(n int, edges [][]int, source int, destination int) bool {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(a, b int) {
		ra, rb := find(a), find(b)
		if ra == rb {
			return
		}
		if rank[ra] < rank[rb] {
			parent[ra] = rb
		} else if rank[ra] > rank[rb] {
			parent[rb] = ra
		} else {
			parent[rb] = ra
			rank[ra]++
		}
	}

	for _, e := range edges {
		union(e[0], e[1])
	}
	return find(source) == find(destination)
}

class Solution {
public:
    vector<int> parent, rankv;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (rankv[ra] < rankv[rb]) parent[ra] = rb;
        else if (rankv[ra] > rankv[rb]) parent[rb] = ra;
        else {
            parent[rb] = ra;
            rankv[ra]++;
        }
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        parent.resize(n);
        rankv.assign(n, 0);
        iota(parent.begin(), parent.end(), 0);

        for (auto &e : edges) unite(e[0], e[1]);
        return find(source) == find(destination);
    }
};

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: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            ra, rb = find(a), find(b)
            if ra == rb:
                return
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1

        for u, v in edges:
            union(u, v)

        return find(source) == find(destination)

var validPath = function(n, edges, source, destination) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);

  const find = (x) => {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  };

  const union = (a, b) => {
    let ra = find(a), rb = find(b);
    if (ra === rb) return;
    if (rank[ra] < rank[rb]) {
      parent[ra] = rb;
    } else if (rank[ra] > rank[rb]) {
      parent[rb] = ra;
    } else {
      parent[rb] = ra;
      rank[ra]++;
    }
  };

  for (const [u, v] of edges) union(u, v);
  return find(source) === find(destination);
};