并查集

2026-03-062026-04-25

线下模版

普通并查集

vector<int> fa, sz;

void init(int n) {
  for (int i = 1; i <= n; i ++) {
    fa[i] = i;
    sz[i] = 1;
  }
}

int find(int u) {
  if (fa[u] == u) return u;
  return fa[u] = find(fa[u]);
}

void unite(int u, int v) {
  int from = find(u), to = find(v);
  if (from == to) return;
  if (sz[from] > sz[to]) swap(from, to);
  fa[from] = to;
  sz[to] += sz[from];
}

bool is_united(int u, int v) {
  return find(u) == find(v);
}

vector<vector<int>> group() {

}

带边权并查集

核心思想是：每一个节点维护一个到父节点的权值，路径压缩时沿途累加权值 weight[u] = val[u] - val[root] val[u] = val[root] + weight[u]

vector<int> fa, sz, weight;

void init(int n) {
  fa.resize(n + 1);
  sz.assigin(n + 1, 1);
  weight.resize(n + 1, 0);
  iota(fa.begin(), fa.end(), 0);
}

int find(int u) {
  if (fa[u] == u) return u;
  int anc = find(fa[u]);
  weight[u] += weight[fa[u]];
  return fa[u] = anc;
}

bool unite(int u, int v, int w) { // u -> v
  int from = find(u), to = find(v);
  if (from == to) return weight[u] - weight[v] == w;
  int exp_to = to;
  if (sz[from] > sz[to]) {
    swap(from, to);
  }
  // val[u] - val[from] = weight[u]
  // val[v] - val[to] = weight[v]
  // val[u] - val[v] = w
  // val[from] - val[to] = ? = weight[from]
  sz[to] += sz[from];
  if (exp_to == to) {
    weight[from] = weight[v] - weight[u] + w;
  } else {
    weight[from] = weight[u] - weight[v] - w;
  }
  fa[from] = to;
  return 1;
}

bool is_united(int u, int v) {
  return find(u) == find(v);
}

其他类型并查集线下模版还没总结完