最近在图论这一块总遇到判断连通问题,判断图是否连通,可以用两种简单的方法(我目前知道的)—并查集和DFS,其中并查集可能更好理解,并查集的思路:并查集可以分为两个过程一个是归并过程一个是查找过程,其中在一个图中,一开始声明一个bin数组把所有的结点都指向结点自己本身,也就是bin[i]=i;i代表结点的序号,之后每次遇到一条连通的道路,比如a-b首先需要把a和b指向的根的结点找出来(当然一开始的时候都指向自己,之后合并一些结点之后指向的就是某一个根结点了),之后把a的根结点数值指向b的根结点数值,如此反复之后,所有连通的点都指向一个根节点。代码如下:
#include<iostream>
int find(int t)
{
r=t;
while(bin[r]!=r)
{
r=bin[r];
}
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx=find(x),fy=find(y);
if(fx!=fy)
{
bin[fx]=fy;
}
}
分享到:
相关推荐
并查集算法PKU解题报告 PKU1182 PKU1611 PKU2524
并查集算法思想 详细讲解并查集的具体细节,学习算法的好东西阿
.net 并查集算法例子,简单的一个食物链程序,随便写了写,练习用的。
并查集算法结课,内容丰富,含有例题剖析。
并查集基础 合并,插入,压缩路径 ACM算法
PKU中一些数据结构基本算法题的java实现,包括DIJ、PRIM、二叉查找树、并查集、动态规划、KMP、匈牙利算法、深搜广搜等
ACM高效, 常用算法 ,常见题型分析,比较好的资料,建议下载,好好分析一下
并查集(算法+模板+讲解)
详细讲解了并查集算法,有图解,通俗易懂。
杭州电子科技大学,王然的数据结构课程设计作业,关于图的城市之间一条路径上最大值与最小值之差
并查集的基础直观的介绍,相信能帮助你早日掌握它
并查集 DFA
并查集实现,带路径压缩和template,高效查找神器!注:库里面如果没有unordered_map,可以换成hash_map或者map
算法与数据结构:并查集实现的方法,以及ACM并查集的一些例子
然后基于并查集算法结合定义的最小区域距离值和灰度差分值将目标雪糕棒表面满足预设阈值条件的像素点合并起来,即将上一步骤预处理所得图像分割成了若干子区域;最后根据定义的约束集合对各子区域进行筛查以去除其中...
主要是简单的并查集算法实现,对于喜欢在网站上刷题的同学。
并查集算法的经典归纳!