💬 Discord
Sign In
NeetCode #577LC-261MediumGraphsBlind 75NC 150NC 250
← Back to All Problems

#577 · #261 · Graph Valid Tree(以图判树)

📌 Problem Statement & Constraints

You are given n nodes labelled 0..n-1 and a list of undirected edges. Return whether the edges form a valid tree. Constraints: 1 <= n <= 2000, 0 <= edges.length <= 5000.

💡 Core Algorithmic Approaches

  1. A tree has exactly n - 1 edges and is fully connected.
  2. So the first check is len(edges) == n - 1; combined with connectivity, that rules out both cycles and disconnection.
  3. Then union-find: if any edge connects two already-connected nodes, there is a cycle.
  4. Alternatively, count connected components with union-find and require exactly one.

💻 Benchmark Python3 Implementation

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False                   # a tree has exactly n-1 edges
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path halving
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False               # adding this edge creates a cycle
            parent[ra] = rb
        return True                        # n-1 edges and no cycle -> connected


# Component-counting variant
class Solution2:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        parent = list(range(n))

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

        components = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                components -= 1
        return components == 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E * alpha(V)): effectively linear with union-find.
💾 Space Complexity
O(V) for the parent array.

⚠️ Interview Pitfalls & Follow-ups

  • Only checking for cycles: a disconnected graph with no cycle would pass; the n - 1 edge count (plus acyclicity) is what guarantees connectivity.
  • Using n - 1 edges as the sole test: a graph can have n - 1 edges and still contain a cycle plus a disconnected component.
  • Forgetting path compression: the find operations degrade toward O(n).
  • Treating the input as directed: the edges are undirected.