本文主要介绍解决动态连通性一类问题的一种算法，使用到了一种叫做并查集的数据结构，称为Union-Find。更多的信息可以参考Algorithms 一书的Section 1.5，实际上本文也就是基于它的一篇读后感吧。原文中更多的是给出一些结论，我尝试给出一些思路上的过程，即为什么要使用这个方法，而不是别的什么方法。我觉得这个可能更加有意义一些，相比于记下一些结论。 关于动态连通性我们看一张图来了解一下什么是动态连通性： 假设我们输...
在我看来，简单的并查集算法的问题主要分为几步。初始化 开始合并 寻找最后有多少个根节点 用一个例题来说明比较容易理解。例： 描述 有n个人，编号1-n。 现在有一个舞会，在舞会上，大家会相互介绍自己的朋友。 即： 如果a认识b，b认识c。那么在舞会上，a就会通过b认识到c。 现在，给出m个关系 每个关系描述：a b 表示 编号为a和编号为b的人是朋友关系。 格式 输入格式 输入n和m 接下来m行，每行为a b 输出格式 最后问，会有多少个...
目录 算法介绍 wiki 通俗解释算法实现（C语言） 算法实战 算法介绍 wiki 并查集 通俗解释 零基础学并查集算法 算法实现（C语言）Find函数(未采用路径压缩)int Find(int x) {int r = x;while(pre[r] != r){r = pre[r];}return r; }Find函数(路径压缩递归实现)int Find(int x) {if(pre[x] == x) return x;else{pre[x] = Find(pre[x]);return pre[x]; } }Find函数(路径压缩非递归实现)int Find(int x) {int r = x;while(pre[r] != r...