261. Graph valid tree
Tags:
Medium
Skills:
GraphTree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
💡
Một đồ thị không hướng (undirected graph) được xem là một tree nếu nó không có cycle (chu trình) và graph phải là connected graph (đồ thị liên thông)
Problem
Đề bài yêu cầu cần kiểm tra graph có phải là một valid tree hay không. Một valid tree cần phải thỏa mãn điều kiện:
- Không có cycle
- Tất cả các đỉnh đều được kết nối (đồ thị liên thông)
Approach
- Kiểm tra số cạnh
- Kiểm tra chu trình và tính liên thông
- Không có chu trình: Duyệt qua đồ thị bằng DFS hoặc BFS, nếu phát hiện một đỉnh đã được thăm trước đó mà không phải là cha của đỉnh hiện tại, thì có chu trình.
- Liên thông: Đảm bảo rằng tất cả các đỉnh đều được duyệt qua trong một lần duyệt DFS hoặc BFS.
- Union-Find (Disjoint Set Union)
- Sử dụng thuật toán Union-Find để kiểm tra:
- Nếu hai đỉnh của một cạnh đã thuộc cùng một tập hợp, thì có chu trình.
- Sau khi xử lý tất cả các cạnh, nếu chỉ còn đúng một tập hợp, thì đồ thị liên thông.
💡
Một cây với n đỉnh sẽ có đúng n−1 cạnh. Nếu số cạnh khác n−1, ta có thể kết luận ngay rằng đồ thị không phải là cây.
Solution BFS
💡
TC: O(N + E)
SC: O(N + E)
Với
- N là số đỉnh
- E là số cạnh
typescripttypescript
1function validTree(n: number, edges: number[][]): boolean {
2 if (edges.length === 0 && n === 1) return true
3 if (edges.length !== n - 1) return false
4
5 const graph: Map<number, number[]> = new Map();
6
7 for (let i = 0; i < n; i++) {
8 graph.set(i, []);
9 }
10
11 for (const [source, destination] of edges) {
12 graph.get(source)!.push(destination);
13 graph.get(destination)!.push(source);
14 }
15
16 const visited: Set<number> = new Set();
17 const queue: number[] = [0]
18
19 while (queue.length > 0) { // O(v)
20 const node = queue.shift()!;
21
22 const neighbors = graph.get(node)! || [];
23 for (const neighbor of neighbors) { // O(e)
24 if (!visited.has(neighbor)) {
25 visited.add(neighbor)
26 queue.push(neighbor);
27 }
28 }
29 }
30
31 return visited.size === n;
32}Solution with Union-Find
💡
Time complexity: ~ O(1), which a(N) is reverse ackermann function
Space complexity: O(n), which n is maintain UnionFind class
typescripttypescript
1class UnionFind {
2 parent: number[]
3 rank: number[]
4 constructor(size: number) {
5 this.parent = Array.from({ length: size }, (_, i) => i);
6 this.rank = Array(size).fill(0);
7 }
8
9 find(x: number): number {
10 if (this.parent[x] !== x) {
11 this.parent[x] = this.find(this.parent[x]);
12 }
13 return this.parent[x];
14 }
15
16 union(nodeA: number, nodeB: number): boolean {
17 const rootA = this.find(nodeA);
18 const rootB = this.find(nodeB);
19
20 if (rootA === rootB) return false;
21
22 if (this.rank[rootA] < this.rank[rootB]) {
23 this.parent[rootA] = rootB;
24 } else if (this.rank[rootA] > this.rank[rootB]) {
25 this.parent[rootB] = rootA
26 } else {
27 this.parent[rootB] = rootA;
28 this.rank[rootA]++;
29 }
30
31 return true;
32 }
33}
34
35function validTree(n: number, edges: number[][]): boolean {
36 if (edges.length !== n - 1) return false;
37 const uf = new UnionFind(n);
38
39 for (const [source, destination] of edges) {
40 if (!uf.union(source, destination)) {
41 return false
42 }
43 }
44
45 return true
46};💡
Tổng kết ý tưởng
- Kiểm tra số cạnh phải đúng bằng n - 1
- Dùng Union-Find để phát hiện chu trình
- Nếu không có chu trình và đúng số cạnh, đồ thị là cây hợp lệ
