数据结构-并查集

并查集

• 并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题

makeSet(s)

：建立一个新的并查集，其中包含 s 个单元素集合。

union

：将两个子集合并成同一个集合。

find(x)

确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

并查集的优化

1、路径压缩

我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了

int getfather(int v)
{
    if (father[v]==v)
      return v;
    else
    {
        father[v]=getfather(father[v]);//路径压缩
        return father[v];
     }
}

2、Rank合并

合并时将元素所在深度小的集合合并到元素所在深度大的集合。

void judge(int x ,int y)

{
     fx = getfather(x);
     fy = getfather(y);

     if (rank[fx]>rank[fy])
        father[fy] = fx;
     else
     {
        father[fx] = fy;
        if(rank[fx]==rank[fy])
           ++rank[fy]; //重要的是祖先的rank，所以只用修改祖先的rank就可以了，子节点的rank不用管
     }
}