并查集
2021-04-09 本文已影响0人
吴健民IT
并查集其实是用一个数组来实现的:int father[N];
father[i] 表示元素 i 的父亲结点
对于同一个集合来说只存在一个根结点,且将其作为所属集合的标识。
初始化:
查找:
合并:
只有当两个元素属于不同集合时才能合并,而合并的过程一般是把其中一个集合的根结点指向另一个集合的根结点
路径压缩:
查找:
并查集其实是用一个数组来实现的:int father[N];
father[i] 表示元素 i 的父亲结点
对于同一个集合来说只存在一个根结点,且将其作为所属集合的标识。
初始化:
查找:
合并:
只有当两个元素属于不同集合时才能合并,而合并的过程一般是把其中一个集合的根结点指向另一个集合的根结点
路径压缩:
查找: