关键词：
好吧，什么垃圾并查集，并查集什么的都是铁憨憨<+__+>
现在开始复习回忆：（新手，有错误望指正）
什么叫做并查集，并查集就是一个集合问题，其实最主要的就是知道并查集是一个求解集合数目的问题，具体的操作方法有点飘。
或者这样理解：——并查集通过一个一维数组来实现，其本质是维护一个森林。（好吧，我也不是很理解），我的理解就是通过一维数组来实现，子节点与父节点之间联系，然后查找集合个数。。。。。。。
好吧，不清楚，如果看了前面你很懵逼，那就全都忘了吧，，，
接下来才是正餐：https://blog.51cto.com/ahalei/2348145
直接上代码：
题目是杭电的畅通工程：http://acm.hdu.edu.cn/showproblem.php?pid=1232
#include<stdio.h> int fa[1001]=0; void zore(int n)//未知量用n表示，初始化 for(int i=1;i<=n;i++) fa[i]=i; int find_father(int x)//返回老大，或者说是根节点 if(fa[x]== x) return x; else fa[x]=find_father(fa[x]);//优化路径 return fa[x]; void unions(int n,int m) if(find_father(n)!=find_father(m)) fa[find_father(m)]=find_father(n); int main() int n,m; while(scanf("%d %d",&n,&m)&&n) int sum=0; zore(n); while(m--) int a,b; scanf("%d %d",&a,&b); unions(a,b); for(int i=1;i<=n;i++) if(fa[i]==i) sum++; printf("%d\n",sum-1); return 0;
现在我们把代码拆开来说：
int main()
int n,m;//题目中的n代表城市个数，m代表道路数
while(scanf("%d %d",&n,&m)&&n)
int sum=0;//用来预装需要修的路数
zore(n);//调用初始化函数，来使我们的一维数组初始化
while(m--)//输入m条路
int a,b;//a，b分别代表道路的起始城市的标号
scanf("%d %d",&a,&b);
unions(a,b);//合并有相邻道路的城市，为最后计算道路数做准备：比如最后如果只有两个集合，只需要修一条路；三个集合两条路的思想。
for(int i=1;i<=n;i++)
if(fa[i]==i)//寻找到底有几个独立集合
sum++;
printf("%d\n",sum-1);
return 0;
接下来：
int fa[1001]=0;
void zore(int n)//初始化作用，这点很重要，因为这个操作为我们接下来的操作提供了数据
for(int i=1;i<=n;i++)
fa[i]=i;
再接下来：
int find_father(int x)//这个very very重要
//作用是查找根结点，父节点...>如果你看过第一篇文章，你就把他理解成最大的BOOS就好了
if(fa[x]== x)如果查找点自己就是自己的最大BOOS，则返回
return x;
else
fa[x]=find_father(fa[x]);//优化路径，其实 是一个递归调用
return fa[x];//优化过后改变了树的结构， 子节点很多直接变成了根结点
再接下来再：
void unions(int n,int m)
if(find_father(n)!=find_father(m))//合并操作..>其实就是当两个人的老大不一个人的时候，然而却需要建立联系，好吧，这个时候两个人就要开始干架了，最直接的方法是
fa[find_father(m)]=find_father(n);//直接让两个人的老大来谈话，让一个老大认另一个人的老大为老大，此时他们就属于同一个集合，此时就消除了集合间的隔离，或者说
//合并了两个集合
void unions(int x,int y)
int b1=find_father(n);//或者变成这样，x市到y市之间有一条路，查询x与y市的老大是谁
int b2=find_father(m);
if(b1!=b2)//判断x与y市在不在一个集合
fa[b1]=b2;//如果不在，合并
数据结构学习--并查集(代码片段)
概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情
数据结构学习--并查集(代码片段)
概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情
数据结构学习--并查集(代码片段)
概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情
并查集(代码片段)
主要内容本文主要记录并查集的基本实现方法，并逐步将一些例题填充到文章中。并查集能做什么并查集可以：1.合并集合2.查找两个元素是否在同一个集合内3.集合数量4.确定元素属于哪个集合。完整代码示例classUFpublic:UF();UF(int... 查看详情
并查集——入门学习（java代码实现）(代码片段)
UnionSet.javaimportjava.util.Vector;publicclassUnionSetVector<Integer>rank=newVector<>();Vector<Integer>p=newVector<>();publicUnionSet(intsize)rank.setSize(size);p.setS 查看详情
「学习笔记」tarjan求最近公共祖先(代码片段)
Tarjan算法是一种离线算法，需要使用并查集记录某个结点的祖先结点。并没有传说中的那么快。过程将询问都记录下来，将它们建成正向边和反向边。在dfs的过程中，给走过的节点打上标记，同时维护并查集，这里利用了回溯的... 查看详情
并查集(代码片段)
...们看两道题 亲戚 朋友 显然我们需要并查集。 So,什么是并查集？ 并，就是合并关系（也就是认祖宗）。查，就是查找关系（就是看祖宗是不是一个人）。集，是因为它是个集合。 并查集怎么写呢... 查看详情
并查集的学习和模拟实现(代码片段)
并查集将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这... 查看详情
银河英雄传说-带权并查集(代码片段)
...ww.luogu.org/problemnew/show/P1196 Summarize： 1.此题为带权并查集，需要两个数组，每列长度由下标第一位根节点记录，另外一个数组记录每个节点在当前队列中所处位置； 2.只要注意find函数中位置的更新操作； 附代码：... 查看详情
带权并查集&&并查集(代码片段)
并查集一般的并查集主要记录节点之间的链接关系，而没有其他的具体的信息，仅仅代表某个节点与其父节点之间存在联系，它多用来判断图的连通性主要操作有：初始化把每个点所在集合初始化为其自身。通常来说，这个步骤... 查看详情
tarjan模板，高级并查集(代码片段)
HDU1269评论区居然有人说用并查集过了，其实回想一下求无向图的连通分量，就是并查集，求有向图的话，就要用到这个算法，或者Kosaraju。再回想一下，Tarjan确实比较像并查集，我在第一次写的时候就有这种感觉请看：这是我在... 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
数据结构——并查集的详细解析和实现(代码片段)
...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情
关于最小生成树(并查集)prime和kruskal(代码片段)
适合对并查集有一定理解的人. 新手可能看不懂吧....并查集简单点说就是将相关的2个数字联系起来比如 房子 1 2 3 4 5 6能通向的房子&nb... 查看详情
并查集-leetcode题目总结(代码片段)
本文记录了有关并查集在leetcode中的相关情况，如果有同学在做相关的内容，可以邮件（zhaoliang619960421@outlook.com）或微信（BestCoder_BestLife）与我联系本文参考了以下的相关文档，在此对文档作者表示... 查看详情
数据结构学习--并查集(代码片段)
概念并查集(UnionFind)是一种由孩子指向父亲的树结构，可以高效的处理连接问题(CollectionProblem)。比如：快速判断网络(抽象概念)中节点间的连接状态。对于一组数据，并查集主要支持两个操作：union(p,q);在并查集内... 查看详情