并查集

原理

见《进阶指南》第192页。

代码

int f[N];
int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}
bool query (int x, int y) {
    return find(x) == find(y);
}
for (int i = 1; i <= n; ++ i) f[i] = i;