c语言数据结构之并查集 总结

并查集(Union-Find Set): 一种用于管理分组的数据结构。它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。 注意:并查集不能将在同一组的元素拆分为两组。 并查集的实现: 用树来实现。 使用树形结构来表示以后,每一组都对应一棵树,然而我们就可以将这个问题转化为树的问题了,我们看两个元素是否为一组我们只要看这两个元素的根是否一致。显然,使用树形结构将问题简单化了。合并时是我们只需要将一组的根与另一组的根相连即可。 并查集的核心在于,一棵树的所有节点根节点都为一个节点。使用Find函数查询时,也是查询到这个节点的根节点。 一行并查集: int