-
Notifications
You must be signed in to change notification settings - Fork 0
121 — Graph Valid Tree
LeetCode 261 · Medium. Given n nodes labeled 0 to n - 1 and a list of undirected edges, determine if these edges form a valid tree.
A valid tree with n nodes has exactly two properties: it's fully connected (every node reachable from every other), and it has no cycles. There's a shortcut buried in graph theory that collapses both checks into something simpler: for an undirected graph with n nodes, having exactly n - 1 edges and being connected is equivalent to being a valid tree — a connected graph with n - 1 edges can't have a cycle (adding any cycle would require an extra edge beyond what's needed to connect everything), and it can't be missing anything either (with n - 1 edges and no cycle, everything reachable must already form a single connected block). So instead of a separate cycle-detection pass and a separate connectivity pass, one pass answering "does every union succeed, and are there exactly n - 1 edges" answers both at once.
"Do these edges form a valid tree — connected, with no cycles?" is the cue for Union-Find: reject immediately if the edge count isn't exactly n - 1, then union every edge — if any union ever fails (both endpoints already connected), that's a cycle, and the graph isn't a valid tree.
Build an adjacency list, then check the edge count and run BFS from node 0, tracking visited nodes in a linear-scan array rather than an O(1)-indexed structure. (A connected graph with exactly n - 1 edges is guaranteed to be cycle-free, so no separate cycle check is needed once both facts are confirmed.)
func validTreeBruteForce(_ n: Int, _ edges: [[Int]]) -> Bool {
guard edges.count == n - 1 else { return false }
if n == 1 { return true }
var adjacency = Array(repeating: [Int](), count: n)
for edge in edges {
adjacency[edge[0]].append(edge[1])
adjacency[edge[1]].append(edge[0])
}
var visited: [Int] = [] // linear-scan visited set
var queue = [0]
visited.append(0)
var head = 0
while head < queue.count {
let node = queue[head]
head += 1
for neighbor in adjacency[node] where !visited.contains(neighbor) {
visited.append(neighbor)
queue.append(neighbor)
}
}
return visited.count == n
}Big-O: O(n²) — each BFS step's .contains check scans up to n previously-visited nodes.
Union-Find: reject up front unless edges.count == n - 1, then union every edge — if any union ever fails (the two endpoints are already in the same component), a cycle exists and the graph can't be a valid tree.
final class UnionFind {
private var parent: [Int]
private var rank: [Int]
init(_ n: Int) {
parent = Array(0..<n)
rank = Array(repeating: 0, count: n)
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) -> Bool {
let rootX = find(x), rootY = find(y)
if rootX == rootY { return false }
if rank[rootX] < rank[rootY] {
parent[rootX] = rootY
} else if rank[rootX] > rank[rootY] {
parent[rootY] = rootX
} else {
parent[rootY] = rootX
rank[rootX] += 1
}
return true
}
}
func validTree(_ n: Int, _ edges: [[Int]]) -> Bool {
guard edges.count == n - 1 else { return false }
let uf = UnionFind(n)
for edge in edges {
if !uf.union(edge[0], edge[1]) {
return false // cycle detected
}
}
return true
}
// smoke test
print(validTree(5, [[0,1],[0,2],[0,3],[1,4]])) // true
print(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]])) // false - cycle
print(validTree(4, [[0,1],[2,3]])) // false - disconnectedBig-O: O(n · α(n)) time — near-constant per union/find call thanks to path compression and union by rank. O(n) space.
The brute force needs two separate facts confirmed by two different means: an edge-count check for "not too many edges," and a full BFS traversal for "everything's reachable." Union-Find fuses both checks into a single pass over the edges: the edges.count == n - 1 guard rules out having too many or too few edges up front, and then a single failed union call directly signals a cycle — no separate traversal needed at all, since a cycle can only exist if two nodes get connected twice. Once you already know the edge count is exactly n - 1, "no union ever fails" and "the graph is fully connected" turn out to be exactly the same statement, so Union-Find gets both properties confirmed for the price of one pass.
-
Union-Find — the
n - 1edges + no failed union combination is a direct, minimal-code application of everything that chapter covers. - Union-Find Pattern — "a failed union reveals a cycle" is the same recognition used in Redundant Connection, applied here as a validity check instead of a "which edge" question.
-
Graphs — the underlying theorem (connected +
n-1edges ⟺ tree) is basic graph theory, and the brute force's BFS-based connectivity check is the standard technique from that chapter.
Graph Valid Tree is one Union-Find pass doing double duty — reject unless there are exactly n-1 edges, then let a single failed union reveal a cycle, since a valid tree can never let that happen.
- Why is the
edges.count == n - 1check necessary in addition to the union-failure check — construct a small graph with the right edge count but that still isn't a tree, or vice versa, to convince yourself both checks matter. - Why does a connected undirected graph with exactly
n - 1edges necessarily have no cycles? (Hint: think about what a cycle would require in terms of extra edges beyond what's needed to connectnnodes.) - In
validTreeBruteForce, why does checkingvisited.count == nat the end (after a single BFS from node0) correctly detect disconnection, given that the edge-count check already passed?
⬅️ Previous: Number of Connected Components in an Undirected Graph · Next: Word Ladder ➡️