并查集

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

实现方法

采用有根树+路径压缩的方法来存储节点之间的关系，复杂度接近O(n);

初始化

void init()
{
    for(int i=1;i<=n;i++)  pre[i] = i;
    cnt = 0;  //初始化连通分量
}

查询

int find(int node)
{
  int r = node;
  while(pre[r] != r)  r = pre[r];  //迭代到根
  int p;
  while(node != r)   //路径压缩，将同一集合的元素全部指向根部
  {
    p = pre[node];  
    pre[node] = r;
    node = p;
  }
  return r;
}

合并

void join(int a,int b)
{
  a = find(a);
  b = find(b);
  if(a != b)
  {
    pre[b] = a;
  }
}

例题

HDOJ1213 并查集裸题