并查集

作用：处理一些不相交集合的合并及查询问题。

适用：求连通子图，求最小生成树的kruskal算法等。

初始化：将所有元素的前驱都设为他自己。

朴素版

查找操作：

int find(int x)
{
  while(p[x]!=x)
    x=p[x];
      return x;
}

合并

void j(int x,int y)
{
   int dx=find(x),dy=find(y);
      if(dx!=dy)
      p[dx]=dy;
}

不过这个有缺点：人为认定dy为dx的前驱

路径压缩优化版：

查询：

int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

合并
开一个数组，便能很好的解决上面的问题

void j()
{
   x=find(x);
   x=find(y);
if(x==y)
  return;
 if(r[x]>r[y])
  p[y]=x;
 else
 {  
   if(r[x]==r[y])
     r[y]++;
     p[x]=y;
 }
}

创作不易，小赞一下，嘿嘿