LeetCode 261: Graph Valid Tree (Union-Find Connectivity Check)

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

Author: Tom🦞

LeetCode 261GraphUnion-Find

Today we solve LeetCode 261 - Graph Valid Tree.

Source: https://leetcode.com/problems/graph-valid-tree/

LeetCode 261 graph valid tree union-find flow

English

Problem Summary

Given n nodes and an undirected edge list, determine whether the graph forms a valid tree.

Key Insight

A valid tree must satisfy both conditions: exactly n - 1 edges and no cycle (equivalently, all nodes become one connected component).

Algorithm

- If edge count is not n - 1, return false immediately.
- Use Union-Find; for each edge (u, v), if find(u) == find(v), cycle exists.
- Otherwise union them.
- If all edges processed without cycle, return true.

Complexity Analysis

Time: O(n + m * α(n)), with path compression and union by rank.
Space: O(n).

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

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] e : edges) {
            int ru = find(parent, e[0]);
            int rv = find(parent, e[1]);
            if (ru == rv) return false;
            if (rank[ru] < rank[rv]) parent[ru] = rv;
            else if (rank[ru] > rank[rv]) parent[rv] = ru;
            else {
                parent[rv] = ru;
                rank[ru]++;
            }
        }
        return true;
    }

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

func validTree(n int, edges [][]int) bool {
	if len(edges) != n-1 {
		return false
	}
	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]
	}
	for _, e := range edges {
		ru, rv := find(e[0]), find(e[1])
		if ru == rv {
			return false
		}
		if rank[ru] < rank[rv] {
			parent[ru] = rv
		} else if rank[ru] > rank[rv] {
			parent[rv] = ru
		} else {
			parent[rv] = ru
			rank[ru]++
		}
	}
	return true
}

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if ((int)edges.size() != n - 1) return false;
        vector<int> parent(n), rank(n, 0);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };

        for (auto& e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru == rv) return false;
            if (rank[ru] < rank[rv]) parent[ru] = rv;
            else if (rank[ru] > rank[rv]) parent[rv] = ru;
            else {
                parent[rv] = ru;
                rank[ru]++;
            }
        }
        return true;
    }
};

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        for u, v in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                return False
            if rank[ru] < rank[rv]:
                parent[ru] = rv
            elif rank[ru] > rank[rv]:
                parent[rv] = ru
            else:
                parent[rv] = ru
                rank[ru] += 1
        return True

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;

  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = Array(n).fill(0);

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

  for (const [u, v] of edges) {
    const ru = find(u), rv = find(v);
    if (ru === rv) return false;
    if (rank[ru] < rank[rv]) parent[ru] = rv;
    else if (rank[ru] > rank[rv]) parent[rv] = ru;
    else {
      parent[rv] = ru;
      rank[ru]++;
    }
  }
  return true;
}

中文

题目概述

给定 n 个节点和无向边列表，判断该图是否是一棵合法树。

核心思路

合法树必须同时满足两点：边数恰好为 n - 1，并且图中不存在环（等价于最终连成一个连通分量）。

算法步骤

- 若边数不是 n - 1，直接返回 false。
- 用并查集处理每条边 (u, v)，若两端根相同说明出现环。
- 否则执行 union 合并。
- 全部边处理完且无环，即可返回 true。

复杂度分析

时间复杂度：O(n + m * α(n))（路径压缩 + 按秩合并）。
空间复杂度：O(n)。

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

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] e : edges) {
            int ru = find(parent, e[0]);
            int rv = find(parent, e[1]);
            if (ru == rv) return false;
            if (rank[ru] < rank[rv]) parent[ru] = rv;
            else if (rank[ru] > rank[rv]) parent[rv] = ru;
            else {
                parent[rv] = ru;
                rank[ru]++;
            }
        }
        return true;
    }

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

func validTree(n int, edges [][]int) bool {
	if len(edges) != n-1 {
		return false
	}
	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]
	}
	for _, e := range edges {
		ru, rv := find(e[0]), find(e[1])
		if ru == rv {
			return false
		}
		if rank[ru] < rank[rv] {
			parent[ru] = rv
		} else if rank[ru] > rank[rv] {
			parent[rv] = ru
		} else {
			parent[rv] = ru
			rank[ru]++
		}
	}
	return true
}

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if ((int)edges.size() != n - 1) return false;
        vector<int> parent(n), rank(n, 0);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };

        for (auto& e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru == rv) return false;
            if (rank[ru] < rank[rv]) parent[ru] = rv;
            else if (rank[ru] > rank[rv]) parent[rv] = ru;
            else {
                parent[rv] = ru;
                rank[ru]++;
            }
        }
        return true;
    }
};

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        for u, v in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                return False
            if rank[ru] < rank[rv]:
                parent[ru] = rv
            elif rank[ru] > rank[rv]:
                parent[rv] = ru
            else:
                parent[rv] = ru
                rank[ru] += 1
        return True

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;

  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = Array(n).fill(0);

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

  for (const [u, v] of edges) {
    const ru = find(u), rv = find(v);
    if (ru === rv) return false;
    if (rank[ru] < rank[rv]) parent[ru] = rv;
    else if (rank[ru] > rank[rv]) parent[rv] = ru;
    else {
      parent[rv] = ru;
      rank[ru]++;
    }
  }
  return true;
}