最小生成树线性时间随机化算法(A randomized linear-time algorithm to find minimum spanning trees)及其相关工作（其实时间复杂度不是严格线性的，只是期望为线性，别怪我标题党，论文名就是这样起的，逃
在介绍这个算法前，先介绍最小生成树的两个性质
这两条性质都很好理解，以修公路为例，割性质说的是一个已经连接好的城市群要和外界相连，那必然是选择修最便宜的路了，环性质说的是，如果一堆城市可以构成回路，那拆掉最贵那条路，大家还是互联的。（我一直觉得学Prim和Kruskal算法之前应该先学这两条性质，理解了这两条性质，Prim和Kruskal的正确性一目了然）
Borůvka算法就是在这基础上提出的，每一趟Borůvka操作都把与每个点相连的权值最小的边加入最小生成树（把每个点当做子集，应用割性质），然后把每个连通分量缩成一个点，多重边(multiple edge)保留最小的那条，构建一个新图，再对新图做Borůvka操作，直到变成孤立的点。你可以把这个算法过程理解为一个函数反复apply直到收敛的过程，即达到不动点f(x)=x，也可以把它理解为一个递归函数，每一次调用都是先算出一部分边，然后递归求压缩图的最小生成树，最后返回一个最小生成树。
这才只用上割性质啊，那环性质用来做什么的呢？
割性质断言的是某些边一定在最小生成树中，我们用这个断言来构建最小生成树，而环性质断言的是某些边一定不在最小生成树中，既然如此，如果我们能找到这些边，把它从原图中删除，那么原图在进行递归Borůvka操作时，规模就变小了。
于是，随机化的算法是这样做的，先进行两次Borůvka操作，然后在缩点后的图中以一定的规则选择一个子图，计算这个子图的最小生成树，然后根据这个结果，找到环性质断言的那些边（文中称为重边(heavy edge)，顾名思义，太重，不能出现在最小生成树中），从原图中删除，再对原图进行递归调用求解最小生成树。然后一堆balabala概率论分析，balabala引理，最后证明这个的期望复杂度是线性的。
好了，说了这么多，哪些跟Tarjan有关系呢？
最后，看到这个题目有NOI/ACM标签，我瞬间就出戏了。我猜题主是在OI/ACM中学了好几个Tarjan算法，于是对Tarjan心生敬佩之情，然后想了解一下他提出了哪些算法，想一网打尽，学到屠龙之术。我当初做这个算法的Presentation的时候也是这样想的，哇！线性时间的最小生成树！学会了在OI/ACM里岂不是吊打Prim/Kruskal！看完论文之后我才傻眼了，尼玛！这么复杂的过程，写完都比完了！
丢完参考文献就跑
再丢一点相关资料吧
