今天刷论坛发现陆老师说可以分享题目思路,但不能分享oj平台题目代码......
然后楼主就突发奇想,觉得可以分享一下知识点,顺便拉一下同学的仇恨值,绕乱一下秩序
但由于今天是第一天,所以并不知道要分享什么......随便挑了一个,并借鉴了一下老师的讲义
当然这些都是废话,下面才是正文
并查集
并查集(Union Find Set):是一种用于处理分离集合的抽象数据类型。
主要包含2种操作:
① 查询(Find):给定一个元素x,判断其属于哪个集合。
② 合并(Union):给定两个元素x和y,合并x和y所属的集合
并查集的存储
并查集需要存储的主要包括两部分:
① 记录一组分离的S={S1,S2,S3,S4 …, Sm} 。
② 为每个集合设置一个代表来识别,代表只要选择该集合中的某个元素即可,具体是哪一个并不重要。但是要保证在不对集合进行修改时,多次请求某一动态集合的代表时,得到的答案应该是一致的。
并查集的实现,不需要通过编号区分分离集合,而是使用集合中的元素作为代表,且多个分离集合中的元素不能出现重复。
并查集主要操作
初始化、查找和合并。
① 初始化:make-set(x):建立一个新的,只包含元素x的动态集合,x同时也是该集合的代表。要求x没有在其他集合出现过。使用并查集前,必须进行初始化。
(一般情况下,初始化一个数定义一个集合就ok了)
② 查找:find(x):查找元素x所在的集合,此操作返回x所属集合的代表。
③ 合并:union(x, y):合并x所在的集合Sx和y所在的集合Sy为一个新的集合S,该操作返回新集合S的代表。
具体实现方式(树实现)
楼主比较爱用这种方式,所以贴了这种方式
① 初始化:make-set(x):p[x] = x。
② 查找:find(x):向上查找x的双亲,直到根节点,返回根节点的编号。
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
③ 合并:union(x, y):如果x和y属于同一个集合,不做任何操作,返回�所在分离集合树的根,否则将其中一棵分离集合树的根节点的双亲指向另一棵分离集合树的根节点。
int union_set(int a,int b){
a=find(a),b=find(b);
return p[b]=a;
}
正文至此结束
如果大家有什么想“了解”的知识点,题目,可以及时告诉我
但是,如果我也不会......
你有以下两个人选去问 (楼主经常问他们)
1.陆老师(不推荐,脾气暴躁)
2.方大佬(超级推荐)