1. 介绍
并查集(union-find sets)是一种不相交集合,可用树表示。
union的加权规则:在两个树合并(union操作)时,以结点数多的树的root为新树的root;即结点数少的树接在结点数多的树上。
find的压缩规则:在find(x)操作时,沿节点x的parent链域走动,依次将parent链域的结点挂在root下。
2. 问题
2.1 POJ 1611
问题:求包含0元素的集合的结点数。
源代码
#include "stdio.h"
#include "string.h"
int parent[30000];
int find(int x)
{
int root,tail,temp;
if(parent[x]<0)
return x;
else
{
for(root=x;parent[root]>=0;root=parent[root]);
for(tail=x;tail!=root;tail=temp)
{
temp=parent[tail];
parent[tail]=root;
}
return root;
}
}
void root_union(int x,int y)
{
int xroot=find(x);
int yroot=find(y);
if(xroot!=yroot)
{
int temp=parent[xroot]+parent[yroot];
if(parent[xroot]<parent[yroot])
{
parent[yroot]=xroot;
parent[xroot]=temp;
}
else
{
parent[xroot]=yroot;
parent[yroot]=temp;
}
}
}
int main()
{
int n,m,k,x,y;
while(scanf("%d%d",&n,&m)&&(m!=0||n!=0))
{
memset(parent,-1,n*sizeof(int));
while(m--)
{
scanf("%d%d",&k,&x);
for(k=k-1;k>=1;k--)
{
scanf("%d",&y);
root_union(x,y);
}
}
printf("%d\n",-parent[find(0)]);
}
return 0;
}
2.2 POJ 2524
问题:所有不相交集合的个数
源代码
#include "stdio.h"
#include "string.h"
int parent[50000];
int find(int x)
{
int root,tail,temp;
if(parent[x]<0)
return x;
else
{
for(root=x;parent[root]>=0;root=parent[root]);
for(tail=x;tail!=root;tail=temp)
{
temp=parent[tail];
parent[tail]=root;
}
return root;
}
}
void root_union(int x,int y)
{
int xroot=find(x);
int yroot=find(y);
if(xroot!=yroot)
{
int temp=parent[xroot]+parent[yroot];
if(parent[xroot]<parent[yroot])
{
parent[yroot]=xroot;
parent[xroot]=temp;
}
else
{
parent[xroot]=yroot;
parent[yroot]=temp;
}
}
}
int main()
{
int n,m,x,y,i,count,case_num=1;
while(scanf("%d%d",&n,&m)&&(m!=0||n!=0))
{
memset(parent,-1,n*sizeof(int));
count=0;
while(m--)
{
scanf("%d%d",&x,&y);
root_union(x,y);
}
for(i=0;i<n;i++)
{
if(parent[i]<0)
count++;
}
printf("Case %d: %d\n",case_num,count);
case_num++;
}
return 0;
}
分享到:
相关推荐
深入理解并查集算法,细致讲解,专业老师,一步到位 。
注意:并查集不能将在同一组的元素拆分为两组。 并查集的实现: 用树来实现。 使用树形结构来表示以后,每一组都对应一棵树,然而我们就可以将这个问题转化为树的问题了,我们看两个元素是否为一组我们只要看这两个...
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。比如说,我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 主要构成:并查集主要由一个整型数组...
并查集是一种挺高效的数据结构。实现简单,只是所有元素统一遵从一个规律所以让办事情的效率高效起来。这篇文章主要介绍了数据结构与算法——并查集(不相交集合),需要的朋友可以参考下
31 习题9 排序------------------------------------------------------------------------------------34 第1部分 C++基本知识 各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学...
经典算法题每日演练——第十五题 并查集 经典算法题每日演练——第十四题 Prim算法 经典算法题每日演练——第十三题 赫夫曼树 经典算法题每日演练——第十二题 线段树 经典算法题每日演练——第十一题 Bitmap算法 ...
杭州电子科技大学,王然的数据结构课程设计作业,关于图的城市之间一条路径上最大值与最小值之差
第7章 集合与搜索一、复习要点集合是最基本的抽象数据类型之一。本章讨论了集合的三种存储表示:位数组表示、有序链表表示、并查集。在本章的后半部分,讨论了与集合相关
当前已支持数据结构:大根堆、小根堆、并查集 当前计划后续版本更新内容:高精度整数类型(开发中)、KMP算法字符串匹配、AC自动机算法字符串匹配 高精度整数类演示: 时间有限,目前只实现了同号的加法 如果你要...
7.3 并查集 151 7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割...
本书中涉及到的数据结构有栈、队列、链表、树、并查集、堆和图等;涉及到的算法有排序、枚举、 深度和广度优先搜索、图的遍历,当然还有图论中不可以缺少的四种最短路径算法、两种最小生成树算法、 割点与割边算法...
Spark Streaming将数据切分成片段,变成小批量时间间隔处理,Spark抽象一个持续的数据流 称为DStream(离散流),一个DStream是RDD弹性分布式数据集的micro- batch微批次,RDD是分布式集合能够并行地被任何函数操作...
对PT方法进行改进使之与iDistance的索引机制相适应,并融合这两种不同的空间划分策略,提出一种适用于高光谱数据的索引结构。该索引是一种度量空间的高维索引,采用两级空间划分,在处理光谱相似性查询时可同时完成...
介绍这是间隔树数据结构的一种变体,包含此结构的两种类型-段-点树和点-段树。 段点树允许插入段并查询点,而点段树允许插入点并查询段。 所有操作都以O(log(tree size))复杂度运行。 这些树可以通过您要支持的...
└── person_to_movie.csv // 图谱数据集之一 └── person.csv // 图谱数据集之一 └── userdict3.txt // 图谱数据集之一 └── vocabulary.txt // 图谱数据集之一 └── question // 问题模版(项目中...
leetcode括号生成python leetcode English | The LeetCode Top100 questions were completed ...我的第一本算法书 ...数据结构 ...大话数据结构 数据结构与算法分析 算法之美 ...算法与数据结构 ...并查集 Union
当前已支持数据结构:大根堆、小根堆、并查集、Trie、表达式、高精度整数(部分)、线段树、树状数组、栈 当前计划后续版本更新内容:KMP、AC自动机、红黑树、AVL、SBT、Treap、块状数组、Splay、普通二叉查找树、...
2.并查集 3.图 4.链表 5.队列 6.栈 7.树 divide_conquer:分治 1.活动选择问题 2.输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的...
+ [数据结构](#数据结构-1) + [结构联合](#结构联合) + [块状链表](#块状链表) + [动态树](#动态树) + [左偏树](#左偏树) + [跳表](#跳表) + [SBT](#sbt) + [线段树](#线段树) + [单调队列](#单调队列) + ...