首先，先说下感悟吧，最近几天好像找到点感觉，算法应该是先学会敲，再开始学，这样的效果就比较好。
并查集目前最通俗易懂的。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账号...
