c++ - Disjoint set union 数据结构中到代表的距离

Question

来自 cp-algorithms网站:

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

一个不相交的集合结构通常应该按等级或大小和路径压缩使用 union ，就像你的那样，否则它会变得非常慢。
这些操作以与您的问题无关的方式改变路径长度，因此很难想象剩余的路径长度信息对任何目的都有用。
但是，可能存在与“原始路径”相关的有用信息，即您在没有路径压缩或按等级并集的情况下获得的信息，并且可以通过这些操作将这些信息保存在一个额外的字段中。例如，请参阅此答案:How to solve this Union-Find disjoint set problem?