union_find.ts

class DSU {
    private p: number[];

    constructor(n: number) {
        this.p = new Array(n).fill(0).map((_, i) => i);
    }

    find(x: number) {
        while(this.p[x] !== x) {
            x = this.p[x];
        }
        return x;
    }

    union(x: number, y: number) {
        this.p[this.find(x)] = this.find(y);
    }
}