并查集

sLMxf · 2024-02-14 13:35:46 · 算法·理论

有位哲人是这么说的：爸爸的爸爸是爸爸。——哲人

在并查集中，这句话是成立的。

并查集是维护自己“顶头上司”的一种数据结构，定义为 father_i。（简称 fa_i）

例如P1151 亲戚中，就需要用到并查集。

• 初始化
  并查集的初始化如下：fa_i=i。他表示最开始的时候所有人没有关系，自己的“顶头上司”就是自己。

• 查询——顶头上司
  那如何找到自己的“顶头上司”呢？这里就要用到那位哲人的话了——寻找自己直接上司的顶头上司。可以使用递归维护。递归边界就是自己就是顶头上司。

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

  这样的话，时间复杂度最坏是 O(n)，也就是一条链。可以发现，之后就不需要直接存储直接上司了，可以直接存储顶头上司。即 return fa[x]=find(fa[x]); 。

• 合并
  如果直接将 a 合并 b 上，就会脱离原上司，所以直接干狠点，把自己顶头上司合并到新公司里。（顶头上司：？）
  合并的代码如下：

  void Union(int x,int y)
  {
      int fax=find(x);
      int fay=find(y);
      fa[fax]=fay;
  }

• 查询——是否是亲戚
  直接查询顶头上司是否一样即可。

  if(find(x)==find(y))