C语言并查集的非递归实现详解

目录
  • 【算法分析】
  • 【算法代码】
  • 并查集压缩路径非递归写法
  • 参考文章
  • 总结

【算法分析】

经典的递归实现的并查集，在数据规模过大时，可能会爆栈，因此有了并查集的非递归实现。核心代码如下：

int find(int x) {
	int t=x;
	while(t!=pre[t]) t=pre[t];
	while(x!=pre[x]) {
		x=pre[x];
		pre[x]=t;
	}
	return t;
}
void merge(int x,int y) {
	if(find(x)!=find(y)) pre[find(x)]=find(y);
}

【算法代码】

对问题 http://acm.hdu.edu.cn/showproblem.php?pid=1213 利用非递归实现的并查集的代码如下：

#include <iostream>
using namespace std;
const int maxn=1005;
int pre[maxn];
//int find(int x) {
//	if(x!=pre[x]) pre[x]=find(pre[x]);
//	return pre[x];
//}
int find(int x) {
	int t=x;
	while(t!=pre[t]) t=pre[t];
	while(x!=pre[x]) {
		x=pre[x];
		pre[x]=t;
	}
	return t;
}
void merge(int x,int y) {
	if(find(x)!=find(y)) pre[find(x)]=find(y);
}
int main() {
	int T,N,M;
	int p,q;
	scanf("%d",&T);
	while(T--) {
		int ans=0;
		scanf("%d%d",&N,&M);
		for(int i=1; i<=N; i++) pre[i]=i;
		for(int i=1; i<=M; i++) {
			scanf("%d%d",&p,&q);
			merge(p,q);
		}
		for(int i=1; i<=N; i++) {
			if(find(i)==i) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

/*
in:
2
5 3
1 2
2 3
4 5
5 1
2 5
out:
2
4
*/

并查集压缩路径非递归写法

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

参考文章

//www.jb51.net/article/222108.htm

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容!

赞 (0)

相关推荐

  • 北邮考研复试C语言上机题目精选

    查找 题目描述:            输入数组长度 n       输入数组 a[1...n]       输入查找个数m       输入查找数字b[1...m]             输出 YES or NO 查找有则YES 否则NO .      输入:            输入有多组数据.      每组输入n,然后输入n个整数,再输入m,然后再输入m个整数(1<=m<=n<=100).      输出:            如果在n个数组中输出YES否则输出NO.   

  • C语言 经典题目螺旋矩阵 实例详解

    C语言 经典题目螺旋矩阵 实例详解

    C语言 经典题目螺旋矩阵 //N阶螺旋矩阵 #include <stdio.h> #include <stdlib.h> int main() { int N,i,j,n,num=1; int a[10][10]={0}; printf("输入你要输出的几阶中断:"); scanf("%d",&N); for(n=0;n<=N/2;n++) { for(j=n;j<=N-n-1;j++) a[n][j]=num++; fo

  • 一波C语言二元查找树算法题目解答实例汇总

    一波C语言二元查找树算法题目解答实例汇总

    按层次遍历二元树 问题描述:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印.  例如输入: 8 / / 6 10 / / / / 5 7 9 11 输出 8 6 10 5 7 9 11 定义二元树(其实是二元搜索树,但并不遍历算法)的结点为: struct BSTreeNode { int value; BSTreeNode *left; BSTreeNode *right; }; 思路:利用队列的先进先出,很容易实现.每次取出队列的首元素,然后将其左右子女放入队列

  • c语言数据结构之并查集 总结

    并查集(Union-Find Set): 一种用于管理分组的数据结构.它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组. 注意:并查集不能将在同一组的元素拆分为两组. 并查集的实现: 用树来实现. 使用树形结构来表示以后,每一组都对应一棵树,然而我们就可以将这个问题转化为树的问题了,我们看两个元素是否为一组我们只要看这两个元素的根是否一致.显然,使用树形结构将问题简单化了.合并时是我们只需要将一组的根与另一组的根相连即可. 并查集的核心在于,一棵树的所有节点

  • C语言--数字交换题目详解

    C语言--数字交换题目详解

    目录 一.题目分析 二.算法分析和设计 心路历程 位置分析 分析交换算法 回顾总结(问题核心) 三.编写代码 四.出现问题 总结 一.题目分析 大致题意就是通过交换把最小的数放到最前面,最大的数放最后面.另外要求编写三个函数. 二.算法分析和设计 心路历程 题目有四个关键词,最大值和最小值,第一个数和最后一个数.这就是我们分析的重点. 接下来先对最大值和最小值分析,如果两个数的值相同,位置相同,说明所有的数据都相同,我们什么都不用做.如果两个数的值不同,位置肯定也不同,所以最大值和最小值的位置关

  • C语言题目:有多少张桌子--并查集

    目录 [Problem Description]问题描述 [Input]输入 [Output]输出 [Sample Output]样本输出 [Code]代码 总结 [Problem Description]问题描述 Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You

  • C语言并查集的非递归实现详解

    目录 [算法分析] [算法代码] 并查集压缩路径非递归写法 参考文章 总结 [算法分析] 经典的递归实现的并查集,在数据规模过大时,可能会爆栈,因此有了并查集的非递归实现.核心代码如下: int find(int x) { int t=x; while(t!=pre[t]) t=pre[t]; while(x!=pre[x]) { x=pre[x]; pre[x]=t; } return t; } void merge(int x,int y) { if(find(x)!=find(y)) pr

  • java编程实现并查集的路径压缩代码详解

    java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • Linux(Centos7)下redis5集群搭建和使用说明详解

    1.简要说明 2018年十月 Redis 发布了稳定版本的 5.0 版本,推出了各种新特性,其中一点是放弃 Ruby的集群方式,改为 使用 C语言编写的 redis-cli的方式,是集群的构建方式复杂度大大降低.关于集群的更新可以在 Redis5 的版本说明中看到,如下: The cluster manager was ported from Ruby (redis-trib.rb) to C code inside redis-cli. check `redis-cli --cluster h

  • C语言实现字符串字符反向排列的方法详解

    C语言实现字符串字符反向排列的方法详解

    目录 前言 非递归方法 1.循环实现 2.函数实现 递归方法 1.递归方法 2.递归方法 小结 前言 重点的话说在前头,注意不是逆序打印 今天写题,碰到一个很好的题,在这里来个大家做个分享,我会用多种方法来解决 题目具体内容如下: 编写一个函数(递归实现) 实现:将参数字符串中的字符反向排列,不是逆序打印. 要求:不能使用C函数库中的字符串操作函数 但是这里我不会仅仅局限于题目的要求 非递归方法 1.循环实现 1.1循环实现(sizeof) #include <stdio.h> int mai

  • Go语言学习教程之结构体的示例详解

    目录 前言 可导出的标识符 嵌入字段 提升 标签 结构体与JSON相互转换 结构体转JSON JSON转结构体 练习代码步骤 前言 结构体是一个序列,包含一些被命名的元素,这些被命名的元素称为字段(field),每个字段有一个名字和一个类型. 结构体用得比较多的地方是声明与数据库交互时需要用到的Model类型,以及与JSON数据进行相互转换.(当然,项目中任何需要多种数据结构组合在一起使用的地方,都可以选择用结构体) 代码段1:声明一个待办事项的Model类型: type Todo struct

  • C语言实现二叉树链式结构的示例详解

    C语言实现二叉树链式结构的示例详解

    目录 前言 1. 链式二叉树结构 2. 二叉树的遍历 2.1 前序遍历 2.2 中序遍历 2.3 后序遍历 2.4 层序遍历 3. 常见功能 3.1 二叉树结点个数 3.2 二叉树叶子结点个数 3.3 第K层结点的个数 3.4 二叉树的深度 3.5 判断是不是树是不是完全二叉树 3.6 在二叉树中查找值为x的结点 3.7 拿到每一层的数据 4. 二叉树的创建和销毁 4.1 二叉树的创建 4.2 二叉树的销毁 前言 前面我们已经对堆进行学习,堆就是一个顺序结构的二叉树,把数组看成二叉树,下面一起学

  • C语言中函数参数的入栈顺序详解及实例

    C语言中函数参数的入栈顺序详解及实例 对技术执着的人,比如说我,往往对一些问题,不仅想做到"知其然",还想做到"知其所以然".C语言可谓博大精深,即使我已经有多年的开发经验,可还是有许多问题不知其所以然.某天某地某人问我,C语言中函数参数的入栈顺序如何?从右至左,我随口回答.为什么是从右至左呢?我终究没有给出合理的解释.于是,只好做了个作业,于是有了这篇小博文. #include void foo(int x, int y, int z) { printf(&quo

  • python re模块匹配贪婪和非贪婪模式详解

    这篇文章主要介绍了python re模块匹配贪婪和非贪婪模式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 python贪婪和非贪婪 正则表达式通常用于在文本中查找匹配的字符串.Python里数量词默认是贪婪的(在少数语言里也可能是默认非贪婪),总是尝试匹配尽可能多的字符:非贪婪则相反,总是尝试匹配尽可能少的字符.在"*","?","+","{m,n}"后面加上?,使贪婪

  • python语言time库和datetime库基本使用详解

    今天是边复习边创作博客的第三天,我今年大二,我们专业开的有这门课程,因为喜欢所以更加认真学习,本以为没人看呢,看了后台浏览量让我更加认真创作,这篇博客花了2个半小时的时间,结合自己所学,所思,所想写作,目的是为了方便喜欢Python的小白学习,也是一种自我鞭策吧! python语言使用内置time库和datetime库来处理日期时间 相关术语的解释 UTC time Coordinated Universal Time,世界协调时,又称 格林尼治天文时间.世界标准时间.与UTC time对应的是

随机推荐