class UnionFind {
int[] parent;
int[] size;
UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int node) {
if (parent[node] != node) parent[node] = find(parent[node]);
return parent[node];
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
}
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
def find(self, node: int) -> int:
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
final class UnionFind(n: Int):
private val parent = Array.tabulate(n)(identity)
private val size = Array.fill(n)(1)
def find(node: Int): Int =
if parent(node) != node then parent(node) = find(parent(node))
parent(node)
def union(a: Int, b: Int): Boolean =
var ra = find(a)
var rb = find(b)
if ra == rb then false
else
if size(ra) < size(rb) then
val t = ra
ra = rb
rb = t
parent(rb) = ra
size(ra) += size(rb)
true
class UnionFind {
std::vector<int> parent;
std::vector<int> size;
public:
explicit UnionFind(int n) : parent(n), size(n, 1) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int node) {
if (parent[node] != node) parent[node] = find(parent[node]);
return parent[node];
}
bool unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) std::swap(ra, rb);
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
};