2

From cp-algorithms website:

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).

and the following code is given as implementation:

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]++;
    }
}

I don't understand how this distance to representative could be useful because it just represents distance to leader of the set in our data structure which might not be related to our original problem.
I tried several examples to see how distance changes when we do operations like union_sets and make_set but did not figure anything out. My question is what does this "distance to representative" represent or like what is the significance or any use of it. Any help in visualizing or understanding it is appreciated.

4

1 回答 1

2

A disjoint set structure should typically use union by rank or size and path compression, like yours does, or it becomes very slow.

These operations change the path lengths in ways that have nothing to do with whatever your problem is, so it's hard to imagine that the remaining path length information is useful for any purpose.

However, there might be useful information related to the "original path", i.e., the one you would get without path compression or union-by-rank, and this information could be maintained in an extra field through those operations. See, for example, this anwser: How to solve this Union-Find disjoint set problem?

于 2021-08-22T13:48:02.963 回答