はじめに

この記事は新歓ブログリレー2026 50日目の記事です

やったこと

H.Union Sets で Fastest Code を取れました。やった～

Fastest のコード：https://atcoder.jp/contests/code-thanks-festival-2017/submissions/74769295

問題

$N$ 頂点のUnionFindに対しての $M$ 回のUnion操作が行われる過程が与えられる。『ある点 $x,y$ が同じ連結成分に属するようになったのは何回目のUnion操作からであるか？』という質問を $Q$ 回答えてなさい。

この問題は、部分永続UnionFindで愚直に二分探索してもクエリあたり $O(\log N\log M)$ となり全体で $O((M+Q\log M)\log N)$ で求めることができますが、最大で log が2つ付きます。また並列二分探索を行うと、$O((N+M\alpha (N)+Q)\log M)$ で求めることができますが実装がやや複雑になります。

そこで、このブログでは部分永続UnionFindの内部実装に踏み込むことで、前計算 $O(M\log N)$ / クエリ $O(\log N)$ 、全体で $O((M+Q)\log N)$ で解く方法を紹介します。実装も並列二分探索より楽ですし、クエリごとに計算できるためクエリがオンラインで与えられても求められますし、メソッド化できるのでライブラリ化が容易です(使う機会がどれだけあるかって話ですが...)。

部分永続UnionFindの内部実装

部分永続UnionFindでは、以下のような操作が行えます。ここで「t回目までのUnion操作を行った状態」のことを「時刻 $t$ 」と言います。時刻 $t$ では $t$ 回のUnion操作が行われていて

• marge(x,y)：最新の状態に対して、x と y の属する集合をマージする
• root(x,t)：時刻 $t$ において、x の属する連結成分の根を返す
• same(x,y,t)：時刻 $t$ において、x と y が同じ連結成分に属するか判定する

部分永続UnionFindでは、経路圧縮を行わずに Union by size または Union by rank を用います。ここで経路圧縮を行わない場合、「一度その頂点が根になったらそれ以降の変更を受けない」という性質が成り立ちます。

そこで、Union 操作によって根への辺が生えるときに、「その辺がいつ追加されたか」も記録します。(まだその頂点から辺が生えてない場合は $\infty$ を書き込みます。)

イメージ図：

上図は、例えば

6 7
2 5
4 3
2 8
1 7
1 2

というUnionの過程によって得られる状態です。

この図から root(x,t) を求めるときは、「時刻tまでに張られた辺を辿れるだけだどって上にいく」ことを考えます。例えば、root(4, 5) を求めるときは、頂点2から、時刻5以下で張られた辺である限り上に登って行きます。そうすると頂点2→頂点5は行けますが、頂点5→頂点7は行けません。よって、頂点5で止まるので root(4, 5) = 5 になります。この上に上がる処理は高々木の高さだけ行われますが、Union by size より高さが $O(\log N)$ なので、root の計算量は $O(\log N)$ になります。

root(x, t) を求めることができれば、same(x, y, t) の判定もできます。
詳細な実装に関しては、下の参考を見てください。

件の問題は、以上の機能を持つ部分永続UnionFindを使い二分探索をすることで、クエリあたり $O(\log N\log M)$ で求めることができます。

struct PartiallyPersistentUnionFind{
    vector<int> parent;
    vector<int> marge_times;
    int cur_time;
    constexpr static int inf = 1<<30;

    PartiallyPersistentUnionFind(int n) : parent(n,-1), marge_times(n, inf) ,cur_time(0) {}


    int root(int x, int t = inf-1){
        while (this->marge_times[x] <= t){
            x = this->parent[x];
        }
        return x;
    }


    bool marge(int x,int y){
        this->cur_time++;
        int xr = root(x),yr = root(y);
        if (xr == yr){
            return false;
        }
        if (this->parent[xr] > this->parent[yr]){
            swap(xr,yr);
        }
        this->parent[xr] += this->parent[yr];
        this->parent[yr] = xr;
        this->marge_times[yr] = this->cur_time;
        return true;
    }

    bool same(int x,int y,int t = inf-1){
        return root(x,t) == root(y,t);
    }

    // これは二分探索に依るもので、O(log N log M)
    int get_merge_time(int x,int y){
        if (root(x) != root(y)){
            return -1;
        }
        int ng = 0, ok = this->cur_time;
        while (ok - ng > 1){
            int mid = (ok + ng) / 2;
            if (same(x,y,mid)){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }


};

二分探索による提出（68ms）：https://atcoder.jp/contests/code-thanks-festival-2017/submissions/75149691

同じ連結成分になったタイミングの取得

ある2つが同じ連結成分なったタイミングは、つまり root(x, t) == root(y, t) が一致する最小の t を求めることです。これは root の内部実装と同様に上に上っていくことで解決できます。言い換えれば、「この時刻まではくっついてない」という下界を更新していくことによって求めます。

頂点 x と頂点 y があるとします。まず時刻 0 では同じ連結成分に属していません。
このとき、2つの頂点から生える辺の時刻に注目します。この時刻の小さいを $t^{\prime }$ としたとき、$t^{prime}$ 未満の時刻ではこの2点は連結していません。言い換えれば時刻 $t^{\prime }$ 以降になってから同じ連結成分に入る、という下限が分かります。この下限以降では、root の探索でその辺を通るはずです。よって、小さい方の点を更新します。これを繰り返し、2つの点が一致したところが求める点です。

    int get_merge_time(int x,int y){
        int t = min(this->marge_times[x],this->marge_times[y]);

        while (x != y && t != inf){
            if (this->marge_times[x] > this->marge_times[y]){
                swap(x,y);
            }
            t = this->marge_times[x];
            if (t == inf){
                return -1;
            }
            x = this->parent[x];
        }
        return (t==inf ? -1 : t);
    }

これにより、$O(\text{木の高さ})=O(\log N)$ で求められました。

提出（28ms）：https://atcoder.jp/contests/code-thanks-festival-2017/submissions/75149602

そして、この実装で FC が取れました！
自分の次にFCの人の実装もこれと同じ感じでした。定数倍がいいのは...何ででしょうか？
とにかく FC が取れて良かったです。

余談

そもそも僕は Pythonista なので、Pythonで早いデータ構造の方が嬉しんですよね。
ってことで、Pythonでほぼ同じコードを書いたけれども FC にはなりませんでした..なんでや？
提出：https://atcoder.jp/contests/code-thanks-festival-2017/submissions/74974184

結論

部分永続UnionFindを使って二分探索するとき、本当にそのlogって必要ですか？、ということを考えさせられました。

この手法を使えば、任意時刻での x が含まれるサイズを取得できるような永続部分UnionFindを用いて、「ある頂点xを含む連結成分があるサイズk以上になる最小の時刻」とかも、同様に木を上りながら下限を更新することで、クエリあたりの計算量が $O(\log N)$ で求められます。サイズ取得可能な永続UnionFindの実装は参考を見てください。

参考

• 任意時間の要素列挙可能な部分永続UnionFindの実装例
  • 部分永続UnionFindの実装が図解されていて分かりやすいです
  • 任意時刻のサイズ取得にも対応しています。

明日のブログは 俺 です！お楽しみに～