前言:
当前姐妹们对“算法设计与分许”可能比较关注,小伙伴们都想要剖析一些“算法设计与分许”的相关知识。那么小编在网络上收集了一些有关“算法设计与分许””的相关内容,希望同学们能喜欢,兄弟们一起来学习一下吧!并查集学习笔记
并查集(union-find set)是一抽象数据类型。它所处理的是“集合”之间的关系,即动态地维护和处理集合元素之间复杂的关系,当给出两个元素的一个无序对(a,b)时,需要快速“合并”a和b分别所在的集合,这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。
合并元素所在集合、查找元素所在集合
数组实现
并查集支持的操作
MAKE(x):建立一个新的集合,其仅有的成员(同时就是代表)是x。由于各集合是分离的,要求x没有在其它集合中出现过。
UNIONN(x,y):将包含x和y的动态集合(例如Sx和Sy)合并为一个新的集合,假定在此操作前这两个集合是分离的。结果的集合代表是Sx∪Sy的某个成员。一般来说,在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表。此后,由新的集合S代替了原来的Sx和Sy。
FIND(x):返回一个指向包含x的集合的代表。
查找
int find(int x) { //用非递归的实现 while (father[x] != x) x = father[x]; return x; }int find(int x){//用递归的实现 if (father[x] != x){ return find(father[x]); } else{ return x; } }
合并
void unionn(int r1,int r2){ father[r2] = r1; } int main(){ cin >> n >> m; for (i = 1; i <= n; i++) father[i] = i; //建立新的集合,其仅有的成员是i for (i = 1; i <= m; i++) { scanf("%d%d",&x,&y); int r1 = find(x); int r2 = find(y); if (r1 != r2){ unionn(r1,r2); } } cin >> q; for (i = 1; i <= q; i++) { scanf("%d%d",&x,&y); if (find(x) == find(y)){ printf("Yes\n"); } else { printf("No\n"); } } return 0; }
本文由博客一文多发平台 发布!
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #算法设计与分许