261. Graph Valid Tree

Medium

Description

給定 n 個節點和一組無向邊 edges，判斷這些節點和邊是否構成一棵合法的樹。樹的條件：連通且無環。

Example:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true

Intuition#

合法的樹 = 恰好 n-1 條邊 + 圖連通（或等價地，n-1 條邊 + 無環）。

樹的兩個充要條件：(1) 邊數 = n-1 (2) 圖連通
先檢查邊數是否為 n-1，不是直接回 false
再用 DFS/BFS 或 Union-Find 驗證連通性

Approaches#

1: DFS#

概念: 先檢查邊數 = n-1，再從節點 0 做 DFS，確認所有節點都可達
時間複雜度: O(V + E)
空間複雜度: O(V + E)

class Solution {
    fun validTree(n: Int, edges: Array<IntArray>): Boolean {
        if (edges.size != n - 1) return false

        val graph = Array(n) { mutableListOf<Int>() }
        for ((u, v) in edges) {
            graph[u].add(v)
            graph[v].add(u)
        }

        val visited = BooleanArray(n)
        fun dfs(node: Int) {
            visited[node] = true
            for (next in graph[node]) {
                if (!visited[next]) dfs(next)
            }
        }

        dfs(0)
        return visited.all { it }
    }
}

⭐2: Union-Find#

概念: 先檢查邊數 = n-1，逐條邊 union，若任一邊的兩端已在同一集合則有環（非樹）
時間複雜度: O(E * α(n))
空間複雜度: O(n)

class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray

    fun validTree(n: Int, edges: Array<IntArray>): Boolean {
        if (edges.size != n - 1) return false
        parent = IntArray(n) { it }
        rank = IntArray(n)

        for ((u, v) in edges) {
            if (!union(u, v)) return false
        }
        return true
    }

    private fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    private fun union(x: Int, y: Int): Boolean {
        val px = find(x)
        val py = find(y)
        if (px == py) return false
        if (rank[px] < rank[py]) parent[px] = py
        else if (rank[px] > rank[py]) parent[py] = px
        else { parent[py] = px; rank[px]++ }
        return true
    }
}

🔑 Takeaways#

Pattern: 樹的判定 – 邊數 = n-1 + 連通（或無環）
關鍵技巧: 先檢查 edges.size == n - 1 可以提前排除大量不合法情況，簡化後續驗證