algorithm - 如何通过链表实现不相交集数据结构？

我不知道如何用链表实现不相交集数据结构，谁能告诉我？
我对find-set（）在这种实现中如何工作o（1）次感到特别困惑。~

最佳答案

虽然不相交集数据结构通常被解释为一个树林，但它通常是通过数组实现的：一个数组将索引映射到其父级的索引，另一个数组将索引映射到其列组这就消除了很多无意义的开销（在空间和时间上），这在理论上是不相关的，但在实践中却是如此您可能需要一种方法来映射某种对象的索引和实例。
顺便说一下，find在O（1）中不起作用使用秩的技巧可以防止find采用线性时间，但在最坏的情况下，它仍然可以采取对数步数O（α（n））时间是一个摊余时间，很难解释它的来源-你可以找到一个好的但不是线性集联合算法的效率分析[Tarjan]。
有一种方法可以奏效：

disjoint_set {
    int[] parent, rank;
    makeset(int n)
    {
        rank = new int[n];
        parent = new int[n];
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

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

    void union(int x, int y)
    {
        x_root = find(x);
        y_root = find(y);
        if (x_root != y_root) {
            if (rank[x_root] < rank[y_root])
                parent[x_root] = y_root;
            else if (rank[x_root] > rank[y_root])
                parent[y_root] = x_root;
            else {
                parent[y_root] = x_root;
                rank[x_root]++;
            }
        }
    }
}

关于algorithm - 如何通过链表实现不相交集数据结构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20797313/