不相交集:一组彼此没有公共元素的集合。
并查集算法作用与一个不相交集,实际应用中可以在近乎常数的时间内完成下列两种操作:
查找(Find): 确定元素所在的集合。一般用来判断两个元素是否在同一个集合。
合并(Union): 将两个集合合并成一个集合。
//查找: //p[x]的值为x的父节点 int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
用途:
1、维护无向图的连通性。支持判断两个点是否在同一连通块内,和判断增加一条边是否会产生环。
2、用在求解最小生成树的Kruskal算法里面。
模版题:hdu1213
练手:
LA 3644 - X-Plosives
LA3027 - Corporative Network