现在的位置: 首页 > 综合 > 正文

并查集 LA 3644 – X-PlosivesLA3027 – Corporative Network

2018年12月22日 ⁄ 综合 ⁄ 共 351字 ⁄ 字号 评论关闭

不相交集:一组彼此没有公共元素的集合。

并查集算法作用与一个不相交集,实际应用中可以在近乎常数的时间内完成下列两种操作:

        查找(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

抱歉!评论已关闭.