不相交集合联合数据结构中代表的距离

Question

Sometimes in specific applications of the DSU you need to maintain the distance between a vertex and the representative of its set (i.e. the path length in the tree from the current node to the root of the tree).

并给出以下代码作为实现：

void make_set(int v) {
    parent[v] = make_pair(v, 0);
    rank[v] = 0;
}
pair<int, int> find_set(int v) {
    if (v != parent[v].first) {
        int len = parent[v].second;
        parent[v] = find_set(parent[v].first);
        parent[v].second += len;
    }
    return parent[v];
}
void union_sets(int a, int b) {
    a = find_set(a).first;
    b = find_set(b).first;
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = make_pair(a, 1);
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

我不明白这个到代表的距离有什么用，因为它只代表到我们数据结构中集合的领导者的距离，这可能与我们原来的问题无关。
我尝试了几个示例来了解当我们进行 union_sets 和 make_set 等操作时距离如何变化，但没有弄清楚。我的问题是这种“与代表的距离”代表什么或喜欢它的意义或用途是什么。任何有助于可视化或理解它的帮助都将不胜感激。

Answer 1

一个不相交的集合结构通常应该像你的那样使用按等级或大小和路径压缩的并集，否则它会变得很慢。

这些操作以与您的问题无关的方式改变路径长度，因此很难想象剩余的路径长度信息对任何目的都有用。

但是，可能会有与“原始路径”相关的有用信息，即您在没有路径压缩或按等级并集的情况下获得的信息，并且可以通过这些操作在额外的字段中维护此信息.参见，例如，这个答案：How to solve this Union-Find disjoint set problem?

不相交集合联合数据结构中代表的距离

Distance to representative in Disjoint set union data structure

c++

algorithm

disjoint-union

data-structures