并查集

青悠 · 2018-12-14 17:12:48 · 个人记录

并查集

用于集合的查询，合并(连通块的处理)

实现： father[ ] 操作： 集合的建立，元素的查询，集合的合并

• 建立

father[i]=i;

• 查询

int find(int x)
{
    if(father[x]==x) return x;
    father[x]=find(father[x]);  //路径压缩
    return father[x];
}

• 合并

void union(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    {
        father[fx]=fy;
    }
}