【模板】并查集及几种变化

给定n个元素,最初每个元素在一个集合中,要求实现两种操作:

  1. 合并两个元素所在集合
  2. 查询两个元素是否在同一集合

并查集($Union-Find\space Set$,个人常写作$UnionSet$),就是可以合并,可以查询的集合。朴素并查集是最简单的数据结构之一。

我们可以把每个集合进行标号,如果两个元素所在集合标号一样,说明在同一个集合里。

考虑合并操作,如果暴力将其中一个集合中所有元素标号改成另一个,复杂度爆炸。所以我们使用树形结构来维护。如果将两个集合合并,就将两个集合之间连边。查询时找树根即可。

void init() {
  for(int i = 1; i <= num; ++i) {
    father[i] = i;//最初所有元素标号都为自己
  }
}
int find(int son) {//找树根
  while(father[son] != son) son = father[son];
  return son;
}
void join(int a, int b) {//合并
  father[find(a)] = find(b);//合并树根
  return;
}

但是只是这样的话,构造数据是可以将复杂度卡到爆炸的,所以便出现了各种优化:

按秩合并(单次操作复杂度可看作$\Theta(logn)$)

考虑两个集合所在的树的高度depth[a]和depth[b],我们可以将高度小的树根接在高度大的树根上,能比随便接在查询时快一些。

void join(int a, int b) {
  a = find(a);
  b = find(b);
  if(depth[a] > depth[b]) std::swap(a, b);
  father[a] = b;
  if(depth[a] == depth[b]) ++depth[b];//只用根记录depth即可
  return;
}

按秩合并不是重点,不会也可以,所以也不重点讲解。重点在路径压缩。

路径压缩(单次操作复杂度极低,可看作$\Theta(1)$)

考虑到一个集合的树只要连通,长成什么样子都是可以的,所以我们可以在find时把一路的father都直接改到根上,以后再查询的时候就能少走不少路。这样,按秩合并也可以舍弃了。

路径压缩并查集的复杂度为$\Theta(\alpha(n))$,其中$\alpha$是$Ackermann$函数的反函数。这个复杂度可近似看作$\Theta(1)$。

//传说中的一行一个并查集
int find(int son) {
  return father[son] == son ? son : father[son] = find(father[son]);
}
void join(int a, int b) {
  father[find(a)] = find(b);
  return;
}

模板:洛谷P3367

代码:

#include<cstdio>

class UnionSet {
 private:
  int *father;
 public:
  UnionSet() : father(NULL) {  }
  UnionSet(int len) : father(NULL) {
    init(len);
  }
  void init(int len) {
    delete[] father;
    father = new int[len + 1];
    for(int i = 0; i <= len; ++i) {
      father[i] = i;
    }
  }
  int find(int son) {
    return son == father[son] ? son : father[son] = find(father[son]);
  }
  void join(int a, int b) {
    father[find(a)] = find(b);
  }
};

int main() {
  int num;
  int open;
  scanf("%d%d", &num, &open);
  UnionSet set(num);
  for(int i = 1; i <= open; ++i) {
    int ope;
    int a, b;
    scanf("%d%d%d", &ope, &a, &b);
    if(ope == 1) {
      set.join(a, b);
    } else {
      puts(set.find(a) == set.find(b) ? "Y" : "N");
    }
  }
  return 0;
}

接下来讲几个并查集的扩展:

联合并查集

又叫关系并查集。正常并查集是维护两个元素在同一集合中,而联合并查集则是将所有元素分为两个(有些题可以更多)部分,所有元素非此即彼。

举个例子:

NOIP2010 关押罪犯

n个罪犯,2个监狱。有些对罪犯如果关在同一个监狱会产生$c_i$的影响。问最优分配下最小的最大影响。

未完待更新