问题描述：

基于双亲表示法存储的折叠规则下的并查集

折叠规则：

如果j是从i到根的路径上的一个节点，并且S.parents[j]≠S.root[i]，则把S.parents[j]置于S.root[i]。就是说，让j的双亲指针直接指向根。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//折叠规则压缩路径法
//包含元素i的树中搜索根，并将从元素i到根的路径上的所有结点都变成根的结点
int collapsingfind(int i)
{
    int j;
    for(j=i;parent[j]>=0;j=parent[j]); //搜索j的根
    while(i!=j)   //向上逐次压缩
    {
        int temp=parent[i];
        parent[i]=j;
        i=temp;
    }
    return j;  //返回根
}

最后更新： 2019年10月14日 20:55

原始链接： http://leiii33.github.io/2019/06/25/bingchaji/