2

cp-algorithms のWeb サイトから:

DSU の特定のアプリケーションでは、頂点とそのセットの代表との間の距離 (つまり、現在のノードからツリーのルートまでのツリー内のパスの長さ) を維持する必要がある場合があります。

次のコードが実装として提供されます。

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 などの操作を行ったときに距離がどのように変化するかを確認するためにいくつかの例を試しましたが、何もわかりませんでした。私の質問は、この「代表者までの距離」が何を表しているのか、またはその意味や用途は何なのかということです。それを視覚化または理解するための助けをいただければ幸いです。

4

1 に答える 1

2

互いに素な集合構造は通常、あなたのようにランクまたはサイズとパス圧縮による結合を使用する必要があります。そうしないと、非常に遅くなります。

これらの操作は、問題とは関係のない方法でパスの長さを変更するため、残りのパスの長さの情報が何らかの目的に役立つとは考えにくいです。

ただし、「元のパス」に関連する有用な情報、つまり、パスの圧縮やランクごとのユニオンなしで得られる情報が存在する場合があり、この情報は、これらの操作によって追加のフィールドに保持される可能性があります。たとえば、この anwser: How to solve this Union-Find disjoint set problem? を参照してください。

于 2021-08-22T13:48:02.963 に答える