{ n: number, operations: [{type:"union"|"find", args: number[]}] }
1function find(x):2 if parent[x] != x:3 parent[x] = find(parent[x]) // path compression4 return parent[x]56function union(a, b):7 rootA = find(a)8 rootB = find(b)9 if rootA == rootB: return10 if rank[rootA] < rank[rootB]:11 parent[rootA] = rootB12 else if rank[rootA] > rank[rootB]:13 parent[rootB] = rootA14 else:15 parent[rootB] = rootA16 rank[rootA]++
1class UnionFind {2 parent: number[];3 rank: number[];45 constructor(n: number) {6 this.parent = Array.from({ length: n }, (_, i) => i);7 this.rank = new Array(n).fill(0);8 }910 find(x: number): number {11 if (this.parent[x] !== x)12 this.parent[x] = this.find(this.parent[x]);13 return this.parent[x];14 }1516 union(a: number, b: number): boolean {17 const ra = this.find(a), rb = this.find(b);18 if (ra === rb) return false;19 if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;20 else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;21 else { this.parent[rb] = ra; this.rank[ra]++; }22 return true;23 }24}