并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

——百度百科

主要操作

• 初始化

  int f[N];
  void Init(int x)
  {
  	for (int i = 1; i <= x; i++)
  		f[i] = i;
  }

  使所有元素都指向自己，将自己作为父节点

• 查找

  int Find(int x)
  {
      if (x == f[x]) return x;
      return Find(x);
  }

• 合并

  void Merge(int x, int y)
  {
      f[Find(x)] = Find(y);
  }

优化

路径压缩

每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快。

第一步，找到根结点。

第二步，修改查找路径上的所有节点，将它们都指向根结点。

——百度百科

• 查找

  int Find(int x)
  {
      if (x == f[x]) return x;
      f[x] = Find (f[x]);
      return f[x];
  }

  或者写成这样：

  int Find(int x)
  {
      if (x != f[x]) f[x] = Find (f[x]);
      return f[x];
  }

  再用二元运算符：

  int Find(int x) { return x == f[x] ? x : (f[x] = Find(f[x])); }

  这么写可以让自己看起来更加大佬

按秩合并

将深度小的树合并到深度大的树上

• 初始化

  void Init(int x)
  {
  	for (int i = 1; i <= x; i++)
  	{
  		f[i] = i;
  		rank[i] = 1;	//深度都初始化为1
  	}
  }

• 合并

  void Merge(int x, int y)
  {
  	int a = Find(x), b = Find(y);	//先找到两个根节点
  	if (rank[a] <= rank[b]) f[a] = b;
  	else fa[b] = a;
  	if (rank[a] == rank[b] && a != b) rank[b]++;	//如果深度相同且根节点不同，则新的根节点的深度+1
  }

  因为是小的直接连接到大的根节点，所以合并时小的那一支的深度+1，只有当两者深度相同时才会产生更大的深度

拓展

种族并查集

通过多个并查集将不同的元素归类，并维护相互之间的关系

例题：洛谷 P2024 食物链

用三个并查集分别表示自己、自己的猎物（自己吃的）以及自己的天敌（吃自己的），同时维护三个并查集，通过他们三者的关系判断当前读入数据是否为真

带权并查集

基于路径压缩，每个节点都记录的是与根节点之间的权值

• 查找

  int Find(int x)
  {
  	if (x != f[x])
  	{
  		int t = f[x];
  		f[x] = Find(f[x]);
  		value[x] += value[t];
  	}
  	return f[x];
  }

• 合并

  void Merge(int x, int y)
  {
      int px = Find(x);
      int py = Find(y);
      if (px != py)
      {
          f[px] = py;
          value[px] = -value[x] + value[y] + s;
      }
  }

习题

A Ubiquitous Religions · POJ 2524

B 食物链 · 洛谷 P2024

C How Many Tables · HDU 1213

D 畅通工程 · HDU 1232

E 人见人爱A^B · HDU 2035

F How Many Answers Are Wrong · HDU 3038