Skip to content

并查集

Find-Union算法实现

以下是带路径压缩的并查集实现，需要背下来。 

int fa[MAXN];

int find(int x) {
  if (x == fa[x])
    return x;
  else
    return fa[x] = find(fa[x]);  // 查找 x 的祖先直到找到代表，顺手路径压缩
}

void union(int x, int y) {
  x = find(x);
  y = find(y);
  fa[x] = y;
}

void init(int size) {
  for (int i = 0; i < size; i++) 
    fa[i] = i;
  return;
}

例题