并查集

并查集用来处理集合的合并和查询的问题，比如需要快速的给出两个元素是否在同一个集合中，并查集可以做到接近O(1)的复杂度。

初始化

由于一开始没有集合合并，所以每个节点指向自己

int data[n];
void init(int n)
{
  for(int i = 0; i < n; ++i) data[i] = i;
}

查找

只要知道两个元素最终指向的节点，就能知道他们是不是在同一个集合中了。所以需要判断它是不是最终的节点，也就是a[i] == i

void find(int a){
  int idx = a;
  while(data[idx] != idx){
    idx = data[data[idx]];
  }
  return idx;
}

可能出现一个问题就是data变成一个静态链表，那查一次就退化到了O(n)，为了防止这种情况可以用到路径压缩。

路径压缩

void find(int a)
{
  if(a != data[a])
    data[a] = find(data[a]);
  return data[a];
}

如图所示，C被改到了直接指向A,这样查询就会变快了。

合并

两个集合合并时，把一个集合指向另一个集合即可。

void union(int a, int b)
{
  int ans_a = find(a);
  int ans_b = find(b);
  if(ans_a != ans_b){
    data[ans_b] = ans_a;
  }
}

这种实现是把集合b指向了集合a，这样也有一个问题，就是如果集合b比集合a更大的话，那么查找的时间就会增加一些，因为查找到b的概率更大。

启发式合并

通常有大小和深度两个评价指标，我们这里采用深度。

int size[n];
int data[n];
void init(int n)
{
  for(int i=0; i < n; ++i){
    data[i] = i;
    size[i] = 1;
  }
}

void union(int a, int b)
{
  int ans_a = find(a);
  int ans_b = find(b);
  if(size[ans_a] < size[ans_b])
  {
    data[ans_a] = ans_b;
    size[ans_b] += size[ans_a];
  }else{
    data[ans_b] = ans_a;
    size[ans_a] += size[ans_b];
  }
}

实际上不采用启发式合并，只采用路径压缩也能达到很好的时间复杂度。