「今天是学习C语言第天」
纸上学来终觉浅，绝知此事要躬行。——陆游「冬夜读书示子聿」#并查集
并查集，英文是DisjointSet或Union-Find或Merge–findset。顾名思义：
1.并查集是围绕数学集合的概念，disjointset是互不相交的集合，集合之间没有相交的元素；
2.并查集很方便实现集合元素的合并和查找，合并是指将相同的集合元素放入同一个集合，查找是给定两个元素可以判断是否在同一个集合中；
3.并查集本质上也是一种树形的数据结构，每个集合可以看作一棵树，所有集合构成森林；
4.并查集可以用树表示，具体来说可以用链表或数组表示
5.并查集效率较高，空间复杂度是O(n)，构建集合的时间复杂度O(n)，查找时间是常数。
#实现要点
使用数组来表示并查集，简单方便。
1.数组parent[]，保存集合各个元素的父亲编号，例如parent=i表示i元素的父亲结点是i，也就是自身，这样数组可以用来保存森林也就是多个树；
2.每个集合构成一棵树，集合中的元素都是这颗树的结点；
3.如果两个元素同属一个集合，则其所在树的根结点相同。
#代码实现
实现有三个部分构成，分别是初始化、查询、合并
1.初始化makeSet(intn)
开始时，建立并查集，包含n个集合元素，每个集合元素的父亲是自身,例如parent[0]=0,parent[1]=1...。
2.查询find(intx)
寻找元素x的所在集合的根结点，沿着元素的父亲结点一直向上查询，直到根结点，根结点的父亲结点指向自身。
查询也可以确定两个元素是否属于同一个集合，如果两个元素的根结点相同，则属于同一个集合。
3.合并union(intx,inty)
合并元素x和y所在集合，分别查询元素x和y的根结点，如果根结点相同，表明两个元素已经合并是同一个集合了，如果不同，则直接将元素x查询的根结点指向元素y即可。
合并操作实际上是将两个子集合并成一个集合。
4.压缩路径
find查询操作时间和树的高度相关，因此压缩树的高度可以优化find查询时间，每次find(intx)查询时，找到根结点以后，直接修改当前集合元素x指向根结点。（或者进一步修改当前集合所有元素指向根结点）
备注：union操作也可以优化，设置辅助数组保存树的高度，合并时将较矮的树合并到较高的树。
#代码实例
给定两个人，判断是否亲戚关系。例如总共10个人，8个亲戚关系，每行两个数表示亲戚关系：
01
23
42
78
27
34
96
54
请问2和9是否亲戚关系。
运行结果：2和9是否是亲戚关系：No.3和7是否是亲戚关系：Yes.
#代码
#includestdio.h#defineMAXSIZEintparent[MAXSIZE];voidmake_set(intn){inti;for(i=0;in;i++)parent=i;}intfind_set(intx){introot=x;while(parent[root]!=root)root=parent[root];//压缩路径parent[x]=root;returnroot;}voidunion_set(intx,inty){intrx,ry;rx=find_set(x);ry=find_set(y);if(rx!=ry)parent[rx]=ry;}intis_same(intx,inty){returnfind_set(x)==find_set(y);}intmain(void){//10个人make_set(10);//8个亲戚关系union_set(0,1);union_set(2,3);union_set(4,2);union_set(7,8);union_set(2,7);union_set(3,4);union_set(9,6);union_set(5,4);//判断是否是亲戚关系printf("2和9是否是亲戚关系：%s.\n",is_same(2,9)?"Yes":"No");printf("3和7是否是亲戚关系：%s.\n",is_same(3,7)?"Yes":"No");return0;}----------End----------
往期精彩推荐：
一万分钟C语言学习计划：开篇
C语言内存管理的两种方式
C89标准库功能简介
C语言链接与存储类型
C语言标准输入输出
C语言入门基本语法
更多