323. Number of Connected Components in an Undirected Graph
Tags:
Medium
Skills:
Graph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu đêm số thành phần liên thông (connected components) trong một đồ thị vô hướng với n đỉnh và danh sách các cạnh. Có hai cách phổ biến để giải.
💡
- DFS/BFS: Duyệt từng node chưa thăm, mỗi lần bắt đầu một DFS/BFS mới thì tăng biến đếm thành phần lên 1
- Union-Find: Gộp các node cùng thành phần với nhau, cuối cùng đếm số lượng root khác nhau là ra số thành phần liên thông
Approach
- DFS/ BFS: dễ code, trực quan, phù hợp cho bài này vì n ≤ 2000.
- Union-Find tối ưu hơn nếu cần xử lý nhiều truy vấn hoặc đồ thị lớn, code cũng khá ngắn gọn.
Time and space complexity
Solution - DFS
typescripttypescript
1function countComponents(n: number, edges: number[][]): number {
2 const graph: Map<number, number[]> = new Map();
3
4 for (const [a, b] of edges) {
5 if (!graph.has(a)) graph.set(a, [])
6 if (!graph.has(b)) graph.set(b, [])
7 graph.get(a)!.push(b);
8 graph.get(b)!.push(a);
9 }
10
11 const vis: Set<number> = new Set();
12 let count = 0;
13
14 function dfs(node: number) {
15 vis.add(node);
16 for (const neighbor of graph.get(node)! || []) {
17 if (!vis.has(neighbor)) {
18 dfs(neighbor);
19 }
20 }
21 }
22
23 for (let i = 0; i < n; i++) {
24 if (!vis.has(i)) {
25 count++;
26 dfs(i)
27 }
28 }
29
30 return count
31};Solution - Union Find
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 find(node: number): number {
9 if (this.parent[node] !== node) {
10 this.parent[node] = this.find(this.parent[node])
11 }
12 return this.parent[node];
13 }
14 union(nodeA: number, nodeB: number): boolean {
15 const rootA = this.find(nodeA);
16 const rootB = this.find(nodeB);
17
18 if (rootA === rootB) return false;
19
20 if (this.parent[rootA] < this.parent[rootB]) {
21 this.parent[rootA] = this.parent[rootB]
22 } else if (this.parent[rootA] > this.parent[rootB]) {
23 this.parent[rootB] = this.parent[rootA]
24 } else {
25 this.parent[rootB] = this.parent[rootA]
26 this.rank[rootA]++;
27 }
28
29 return true;
30 }
31}
32
33function countComponents(n: number, edges: number[][]): number {
34 const uf = new UnionFind(n);
35 for (const [a, b] of edges) {
36 uf.union(a, b)
37 }
38
39 const roots = new Set<number>();
40 for (let i = 0; i < n; i++) {
41 roots.add(uf.find(i));
42 }
43
44 return roots.size;
45};