并查集基础总结

并查集基础总结

首先,先说下感悟吧,最近几天好像找到点感觉,算法应该是先学会敲,再开始学,这样的效果就比较好

并查集目前最通俗易懂的。https://www.cnblogs.com/xzxl/p/7226557.html

先截取一段,你看看这通过故事的手法给并查集讲的多么那啥,老少易懂,妇孺皆知。

并查集由一个整数型的数组和两个函数构成。数组pre[]记录了每个点的前导点是什么,函数find是查找,函数join是合并。

话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢? 我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。 但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?” 这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

并查集基础总结

 

下面我们来看并查集的实现。 int pre[1000];  这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。  

 

好,自己再试着打一遍吧,并查集的优化算法理解,还是灯笼讲的好。

简单的就不打了。

直接上进阶的并查集吧,还是放在克鲁斯卡尔算法;里面搞

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot=0,k=0;//n端点总数,m边数,tot记录最终答案,k已经连接了多少边 
int fat[200010],rank[234124];//记录集体老大 
struct node
{
	int from,to,dis;//结构体储存边 
}edge[200010];
bool cmp(const node &a,const node &b)//sort排序(当然你也可以快排) 
{
	return a.dis<b.dis;
}
int father(int x)//找集体老大,并查集的一部分 
{
	if(fat[x]!=x)   //开始以为递归是最原始的,用while的是效率慢的。。 
	return father(fat[x]);
	return x;
}
void unionn(int x,int y)//加入团体,并查集的一部分 
{
	x=father(x);
	y=father(y);
	if(x==y)
	return ;
	if(rank[x]>rank[y])
		fat[y]=x;
	else 
	{
		if(rank[x]==rank[y])
		rank[y]++;
		fat[x]=y;
	}
}
int main()
{
	scanf("%d%d",&n,&m);//输入点数,边数 
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息 
	}
	for(int i=1;i<=n;i++) 
	{
	fat[i]=i;
	rank[i]=1;//自己最开始就是自己的老大 (初始化)
	}
	sort(edge+1,edge+1+m,cmp);//按权值排序(kruskal的体现) 
	for(int i=1;i<=m;i++)//从小到大遍历 
	{
		if(k==n-1) break;//n个点需要n-1条边连接 
		if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体 
		{
			unionn(edge[i].from,edge[i].to);//加入 
			tot+=edge[i].dis;//记录边权 
			k++;//已连接边数+1 
		}
	}
	printf("%d",tot);
	return 0;
}

其实这才还是入门,下一步普利姆算法,先把算法都过一遍,然后在一个个的专题刷,打怪进阶。

有读者的话,不妨关注一下,我带你们快速入门一个算法。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114885.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • mysql 服务器端命令源码(二) Show authors

    mysql 服务器端命令源码(二) Show authors

  • Java我的高效编程之常用函数

    Java我的高效编程之常用函数

    2020年11月12日
  • Hash算法的讲解[通俗易懂]

    Hash算法的讲解[通俗易懂]散列表,又叫哈希表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。散列表(Hashta

  • PID控制电机转速

    PID控制电机转速转一个PID控制电机的小程序,被PID困扰好多天了,知道它的原理但是一直不明白如何将它运用到电机调速中间去,看了这个程序之后感觉茅塞顿开。原来也并不难^-^转载地址:呃,刚刚不小心把网页关掉了(大写的尴尬)。。。。#include#include#defineucharunsignedchar #defineuintunsignedint#define

  • Android Studio 安装配置教程 – Windows(详细版)

    Android Studio 安装配置教程 – Windows(详细版)准备工作Java环境变量配置好,参考:Java环境变量配置然后首先是安装程序,这里默认不翻墙,使用国内的,:AndroidStudio下载地址,最新版本目前是3.5.2,由于我之前已经下载过了3.5.0了,所以我就不需要再下载3.5.2了,安装双击运行点击Next下一步点击Next下一步默认会给你转到C盘,这里我修改到了G盘(PS:这里一定要改路径,否则随着你开…

  • 笛卡尔与心形线故事_笛卡尔的故事

    笛卡尔与心形线故事_笛卡尔的故事说明写这篇文章是某天看到这样一个公式r=a(1-cosθ),我上网搜了下,原来是笛卡尔心形线的极坐标方程,这个方程里的确有一个浪漫又悲情的爱情故事,感兴趣的朋友可以点这里看看,而至于这个故事是真是假,这并不重要。而这篇文章的目的是要用前端的方式,画出笛卡尔心形线。本来我想,这么经典的公式,网上应该已经有人实现过了的吧。我搜了搜,不得不佩服网友们,有Java实现的,有C#…

    2022年10月16日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号