資料結構

1class NaiveUnionFind {
2  parent: number[];
3 
4  constructor(n: number) {
5    this.parent = Array.from({ length: n }, (_, i) => i);
6  }
7 
8  find(x: number): number {
9    while (this.parent[x] !== x) x = this.parent[x];
10    return x;
11  }
12 
13  union(a: number, b: number): void {
14    const ra = this.find(a), rb = this.find(b);
15    if (ra === rb) return;
16    this.parent[ra] = rb;
17  }
18}
19 
20class UnionFind {
21  parent: number[];
22  size: number[];
23 
24  constructor(n: number) {
25    this.parent = Array.from({ length: n }, (_, i) => i);
26    this.size = new Array(n).fill(1);
27  }
28 
29  find(x: number): number {
30    let root = x;
31    while (this.parent[root] !== root) {
32      root = this.parent[root];
33    }
34    while (this.parent[x] !== root) {
35      const next = this.parent[x];
36      this.parent[x] = root;
37      x = next;
38    }
39    return root;
40  }
41 
42  union(a: number, b: number): void {
43    let ra = this.find(a), rb = this.find(b);
44    if (ra === rb) return;
45    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
46    this.parent[rb] = ra;
47    this.size[ra] += this.size[rb];
48  }
49}