并查集初始化查找合并路径压缩

- 日理万妓 2023-07-04 11:13 19阅读 0赞

/* * 并查集 * * */
    #include <stdio.h>
    int father[7];
    //初始化
    void init()
    { 
        for(int i=1;i<7;i++)
        { 
            father[i]=i;
        }
    }
    //查找根节点
    int findFather(int x)
    { 
        if(x==father[x])
            return  x;
        else return findFather(father[x]);
    }
    //合并集合
    void Union(int x,int y)
    { 
        int faA=findFather(x);
        int faB=findFather(y);
        if(faA!=faB)
        { 
            //根节点不同说明不是同一个集合 进行合并
            father[faA]=faB;
            //faA的根节点设为faB
        }
    }
    //路径压缩
    //1.先查找x根节点
    //2.将查找x路径上所有节点父节点设置为根节点
    void changeFather(int x)
    { 
        int a=x;
        x = findFather(x);
        //修改路径上节点的根节点
        while(a!=father[a])
        { 
            int z=a;
            //回溯父节点
            a=father[a];
            //修改父节点为根节点
            father[z]=x;
        }
    }
    int main()
    { 
       init();
       for(int i=1;i<7;i++)
       { 
           printf("%d-->%d ",i,father[i]);
       }
        printf("\n4的根节点：%d\n",findFather(4));
        //合并集合
        Union(4,6);
        for(int i=1;i<7;i++)
        { 
            printf("%d-->%d ",i,father[i]);
        }
        printf("\n4的根节点：%d\n",findFather(4));
        //路径压缩
        changeFather(4);
        for(int i=1;i<7;i++)
        { 
            printf("%d-->%d ",i,father[i]);
        }
        printf("\n4的根节点：%d\n",findFather(4));
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】并查集(路径压缩)

并查集

客官°小女子只卖身不卖艺/ 2024年04月21日 19:18/ 0 赞/ 50 阅读

相关合并集合(并查集)

合并集合一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。现在要进行 m 个操作，操作共有两种： M a b，将编号为 a 和 b 的两个数所在的集

Myth丶恋晨/ 2024年03月30日 11:36/ 0 赞/ 56 阅读

相关并查集路径压缩

并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中

曾经终败给现在/ 2024年03月16日 23:49/ 0 赞/ 46 阅读

相关并查集快速合并

对于一组数据，并查集主要支持两个动作： union(p,q) - 将 p 和 q 两个元素连接起来。 find(p) - 查询 p 元素在哪个集合中。 is

骑猪看日落/ 2024年03月16日 23:18/ 0 赞/ 44 阅读

相关并查集快速查找

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。 > ... > pri

雨点打透心脏的1/2处/ 2024年03月16日 23:18/ 0 赞/ 22 阅读

相关并查集快速查找

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。 > ... > pri

落日映苍穹つ/ 2024年03月16日 22:49/ 0 赞/ 35 阅读

相关并查集路径压缩（Java 实例代码）

目录并查集路径压缩 Java 实例代码 UnionFind3.java 文件代码： -------------------- 并查集路径压缩并查集里的 fi

我会带着你远行/ 2023年10月14日 21:07/ 0 赞/ 5 阅读

相关并查集初始化查找合并路径压缩

/ 并查集 / include <stdio.h> int father[7]; //初始化 void init() {

- 日理万妓/ 2023年07月04日 11:13/ 0 赞/ 20 阅读

相关【算法】并查集—带路径压缩的按秩合并法

读了《算法导论》的21章：用于不相交集合的数据结构后在这里对并查集算法做一个小结。对于动态集合的表示有多种方法，例如链表和有根树。不论是哪种表示，我们都用一个代表来标识

淩亂°似流年/ 2022年05月31日 02:30/ 0 赞/ 221 阅读

相关并查集系列（路径压缩）

[547. 朋友圈][547.] 难度中等255 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友

水深无声/ 2021年10月03日 02:34/ 0 赞/ 184 阅读