323. Number of Connected Components in an Undirected Graph

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};

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};