Union-Find (DSU)

1class UnionFind {
2  private parent: Map<string, string> = new Map()
3 
4  find(x: string): string {
5    let root = this.parent.get(x) ?? x
6    while (root !== (this.parent.get(root) ?? root)) {
7      root = this.parent.get(root) ?? root
8    }
9    // сжатие пути
10    while (x !== root) {
11      const next = this.parent.get(x) ?? x
12      this.parent.set(x, root)
13      x = next
14    }
15    return root
16  }
17 
18  union(a: string, b: string): void {
19    const ra = this.find(a)
20    const rb = this.find(b)
21    if (ra !== rb) this.parent.set(ra, rb)
22  }
23 
24  connected(a: string, b: string): boolean {
25    return this.find(a) === this.find(b)
26  }
27}