并查集(Union-Find)算法

来源：爱问旅游网

本文转载自csdn另一博主，其原文点。

    public int find(int[] parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }

这个DFS函数可以直接将所经过的所有点的parent设置为根，因此可以忽略原文快结尾处id[i] = id[id[i]]变为爷爷节点这一段。

======分界线 ======

本文主要介绍解决动态连通性一类问题的一种，使用到了一种叫做并查集的，称为Union-Find。

更多的信息可以参考Algorithms 一书的Section 1.5，实际上本文也就是基于它的一篇读后感吧。

原文中更多的是给出一些结论，我尝试给出一些思路上的过程，即为什么要使用这个方法，而不是别的什么方法。我觉得这个可能更加有意义一些，相比于记下一些结论。

关于动态连通性

我们看一张图来了解一下什么是动态连通性：

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文