競プロ覚書：Union-Find まとめ

　競プロで「典型」とされるアルゴリズム Union-Find についてまとめました．Union-Find のイメージ，Union-Find がどんな問題に適用できそうかに焦点を当てました．

　Union-Find を実装する上で重要な，高速化（経路圧縮，マージテクなど）に関する詳しい説明は他の記事に譲っています（筆者の力不足で，上手く言語化できませんでした）．そのため，本記事では Union-Find に関する「お気持ち」程度の解説となっています．厳密なアルゴリズム，計算量の解説は出来ていないので，そういった解説を求めている方は参考記事を参照いただければと思います．また，無駄に長いので，各自必要そうな項目を選んで目次から飛んでください．

概要

　本記事では，「素集合データ構造」から徐々に「Union-Find」について理解できるように解説していきます．

• Union-Find の概要
• 素集合データ構造と Union-Find
• Union-Find とは
• Union-Find 木の実装
• Union-Find 木を使って問題を解く

　以上の流れで解説します．冒頭で書いたようにアルゴリズムの詳細ではなく「適用」を主題としているため，そちらが目的の方は参考資料に飛んでください．お探しの資料があるかもしれません．

　「素集合データ構造と Union-Find」の部分では，そもそも「データ構造」とはなんなのかという基本的な概念から解説しています．これは筆者が知らなかったがために勉強しまとめたもので，初歩的な内容になっています．興味のない方は適当に読み飛ばしていただいて構いません．

Union-Find の概要

　まず，Union-Find のざっくりとしたイメージを解説します．Union-Find は，

• Union：グループを繋げる
• Find：ある要素が同じグループに属するか

という操作（クエリ query、問い合わせなどと呼ぶこともある）を高速に行うための「仕組み」（アルゴリズム）です（以下のスライド p2 ~ p4）．

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

　「グループを繋げる」，「グループに属するか」という二つの操作が Union-Find の軸になるので，これらを念頭に置いた上で Union-Find を解説していきます．

注意

　Union-Find に関する素晴らしい教材（上記のスライド）と問題が AtCoder から提供されています．そちらを参照した方が本記事を読むより効率的で分かりやすい，というのが本記事を書き終わった後に抱いた正直な感想です．本記事は何も分からない筆者自身の勉強履歴を書き起こしたに過ぎない記事なので大分遠回りになっています．

　パッと勉強したい方は，先に示したスライドや以下の問題で勉強した方が時間の無駄にならないと思います．

• AtCoder Typical Contest 001: B - Union

素集合データ構造と Union-Find

　まず，Union-Find の元となるデータ構造である「素集合データ構造」を導入し，それから「Union-Find」を解説していきます．

素集合データ構造

素集合データ構造 - Wikipedia

　素集合 disjoint setとは，互いに素な集合，互いに共通の元を持たない集合のことです．

　素集合データ構造とは，素集合を分割して保持するためのデータ構造のことです．正確には各素集合（各グループ）を木構造として保持するためのデータ構造で，実装では「各木の根を配列に持たせる」ことでこれを実現します（詳しくは実装パートで解説）．また，木構造をいくつか持つことから素集合森と呼ばれることもあります（森：木が複数あるデータ構造）．

　素集合データ構造は，集合の分割をモデル化したものであり，集合の分割を無向グラフの連結成分に対応づけることができます．例えば，競プロでよく見る無向グラフに適用することができます．無向グラフの頂点の個数が入力として与えられ，

• 新たな辺を追加し，連結成分を繋げる（グループを繋げる）
• 2 つの頂点が同じ木に属するか（連結成分か）（ある要素が同じグループに属するか）

という 2 つのクエリに対して処理を高速に行うという問題は素集合データ構造の性質をそのまま使えます（つまり 無向グラフの問題に Union-Find を適用できる）．

　ちなみに，データ構造とは，データ（頂点や元）を効率的に扱うための保持の仕方（配列など）のことです．この言葉を使うと，素集合データ構造とは，「素集合を効率的に扱うために集合の要素を工夫して（配列等を使って）保持する方法」と，噛み砕いて言うことができます（逆に分かりづらいか）．

Union-Find アルゴリズム

アルゴリズムの概要

　Union-Find とは，素集合データ構造に対して適用される効率的なアルゴリズム（操作）の名称です．

• Union：2 つの集合を一つに統合する（2 つの木構造を一つにまとめる）．
• Find：要素が属する集合の代表を見つける（木構造の根を見つける）．2 つの要素が同じ素集合に属するかの判定（同じ根を持つか）にも使われる．

　「グループを繋げる」，「グループに属するか」という操作を実装寄りに説明すると以上のようになります．素集合を上手く保持することで（素集合データ構造では），データに対して 2 つの操作を高速に行うことができます．素集合データ構造は，2 つの操作の名称から，Union-Find データ構造，Union-Find 木（Union-Find 森では？）とも呼ばれます．

言葉の整理

　Union-Find に関する資料で勉強する際に，色んな表現が出てきて混乱したので言葉を整理しておきます．

• 素集合データ構造＝Union-Find 木
• 素集合を分割したもの＝素集合＝集合＝木＝グループ
• 各集合の代表＝木の「根」＝グループの代表

　木構造として保持されている（分割された）集合を「グループ」，「集合」，「木」という言葉を使って簡潔に書いてある記事がいくつか見られました．「グループに属しているかどうか」という記述は Union-Find の操作のイメージがしやすいですし，「木に属しているか」という記述は Union-Find の実装をイメージしやすくなります．どの表現がしっくりくるかというのは人により違いますが，以降本記事では，

• 素集合データ構造：Union-Find 木
• 分割された集合：集合，木
• 各集合の代表：根

と表現することにします．

Union-Find 木の実装

データ構造の実装

　Union-Find 木というデータ構造を実装していきます．データ構造のことを，「データを効率的に扱うための保持の仕方」と説明しましたが，「データ構造を実装する」とは，

• データの保持の仕方
• 保持しているデータに対する操作（メンバ関数）

の二つを構造体やクラスを用いて実装することです*1．

　とても基礎的なことを述べましたが，これはデータ構造全般（キューやスタックなど）に言えることで，データ構造を実装するための枠組みとなります．

Union-Find 木の実装の大枠

　Union-Find 木を，上記に示したデータ構造を実装するための枠組みに当てはめると以下のようになります．便宜的にメンバ関数の名称を変えたり（()内は実装でよく使われる他の関数名），実装すると便利になる関数を加えたりしています．

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

Union-Find 木の実装

• データの保持の仕方
  • 各要素の根を保持する（各要素がどの集合に属するのか）：配列を用いる．
  • 集合のサイズを保持する：配列を用いる（各木のサイズを持っておくと便利）
• 保持をしているデータに対する操作（メンバ関数）
  • merge (Union, unite)：集合（木）を合併する
  • root(Find)：ある要素がどの根に属するか（ある要素がどの集合（木）に属しているか）
  • size：連結成分のサイズはいくらか
  • issame：二つの要素がどの根に属するのか（二つの要素が同じ集合（木）に属するか）

　素集合の各要素は，要素が属する木の根として配列に保持されます（どのグループに属するかを表す）．各操作は上記に書いてある通りです．Union-Find アルゴリズムの Union，Find は，それぞれ名前を変えて merge（Union*2） ，root（Find）となっています（割とよく見る命名）．

実装

実装のポイント：マージテク，経路圧縮

　Union-Find 木の実装で重要な部分は，ここまで何度も出てきたように以下の二つです．

• Union：2 つの集合を一つに統合する（2 つの木構造を一つにまとめる）．
• Find：要素が属する集合の代表を見つける（木構造の根を見つける）．

　そして，これらの操作を高速化し，実用的な計算量まで落とす部分が Union-Find 木の実装のキモとなります．Union，Find のそれぞれに対して，

• Union の工夫：マージテク（大きい方を動かさずに小さい方をくっつける）
• Find の工夫：経路圧縮（集合の要素を根に直接繋ぎかえる．木をフラットに保つ）

という工夫を施すことで， Union-Find アルゴリズムを実用的な計算量まで落とすことができます．

Union-Find アルゴリズムに関する資料

　冒頭に書いた通り，本記事では実装の高速化の部分は解説しません（できません）．その代わりと言っては何ですが，高速化の部分を解説している記事（＋Union-Findの解説記事）をいくつか列挙しておきます．本記事の内容は，ちゃんと勉強したい方にとっては物足りないものだと思うので，以下の記事が参考になれば幸いです．

• Union-Find の実装について

  • 素集合データ構造（Union-Find） 簡潔で分かりやすい説明，綺麗な実装が紹介されています．
  • UnionFindTree に関する知見の諸々 Union-Find 木には，実装のバリエーション（union by rank, union by size），経路圧縮のバリエーション（path compression, path having, path splitting）があり，それらのバリエーションと計算量に関する簡潔な説明がなされています．正直この記事は，Union-Find の応用部分に力を入れていて上級者向けだと思いました（私はこの記事の始めの部分しか読めていないです）．

• マージテクについて

  • "データ構造をマージする一般的なテク" とは？ 秋葉さんの資料．「小さい方を大きい方にくっつける」というマージテクの概念が実装と共に分かりやすく解説されています．

• 経路圧縮について

  • Disjoint-set data structure Wikipedia の解説．正直このページを見れば十分な気がします．三種類の経路圧縮の擬似コードと簡単な説明が載ってます．
  • Union Find（素集合データ構造） この記事でちょくちょく出てくる AtCoder の記事．経路圧縮の内，path compression が載っています．
  • 1.5 Case Study: Union-Find path compression メインですが，下の方に path having，path splitting の説明が少し載ってます（ググると大半が path compression でなかなか他の実装が見当たりませんでした...）．

• その他

  • Union-Find Algorithms 英資料ですが，Union-Find を実装し，そこからどう improvement（高速化）していくかの過程が丁寧に描かれています．

　 Union-Find は有名なアルゴリズムなので探せばいくらでも出てくると思います．気になった方は検索してみてください．

Union-Find 木のソースコード

　実装を示します．satanic さんという方の実装を非常に参考にさせていただきました．

　本記事の Union-Find 木は，

• 実装のポリシー：union by size
• 経路圧縮：path having

で実装されています．理由は自分の中で一番しっくりきたからです．「UnionFindTree に関する知見の諸々」という記事の中に，「好きなパーツを組み合わせて君だけの UnionFindTree を作ろう！」という某ゴスティー二っぽい記述があったので私もそれに従いました．

　以下に実装を示します．コメントアウトしている部分に少しだけ説明を書いてあるので良かったら参考にしてください．

// union by size + path having
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

　基本的な部分のみ補足しておきます．

• par：素集合の要素の親（木構造の根）を配列*3で保持している．初期状態では頂点間の辺は存在せず，孤立した状態のため，自分自身を根として初期化している（par: parent の略）．
• siz：各集合（木）の大きさ．根をたどるとその木の大きさが返されるように実装されている．この配列を用意しておくとある頂点の連結成分の大きさを簡単に求められる．

　以上 Union-Find を実装してみました．メジャーな実装では union by rank + path compression（蟻本はこれらしい） が多いと思いますが，自分の理解しやすいものに合わせると良いと思います．

Union-Find 木で問題を解く

　実際に Union-Find 木を使ってどんな問題が解けるのか簡単に見ていきます．

典型的な考え方：辺を切り離す処理より繋ぐ処理の方が簡単

　問題を解いていく前にポイントを解説します．ABC120 の解説放送で chokudai さんが触れていた話です．Union-Find 木に限らず，グラフを扱う問題の一般的なポイントを紹介します．グラフを扱う問題で，辺を切り離すという処理が出てきた時，

• グラフの辺を切り離す（壊す）処理より繋ぐ処理の方が簡単
• 切り離すしかなかったら繋ぐ処理に言い換えることができる（分離を高速にできるデータ構造 directed-connectivity もあるが AtCoder では扱わない，覚える必要はない by chokudai さん）

と考える，というのがポイントになります．これらのポイントは，

• 繋げていく処理だけを考えるとき，繋げたものだけを考えれば良いので，連結かどうかの判定は簡単
• 辺を壊した後にグラフが連結がどうかは，遠くまで見ないと連結かどうかの判定が難しい．
• 上記の「難しい」というのは，グラフ上を遠くまで探索して連結かどうかを愚直に調べることのできるのは DFS，BFS なので，制約が大きいと計算量的に判定が難しい，という意味．

以上 3 つを考えると意味が分かると思います．繋がっているかどうかの判定は，ここまで見てきた通り，Union-Find 木を使えば簡単にできます（DFS，BFS，ワーシャルフロイド法などでも繋がっているかの判定はできるが，制約が大きくなると計算量的に使えない）．

　このポイントは，例えば「無向グラフが与えられてその辺を壊し，連結かどうかの判定」を行うという典型的な問題に対して適用することができます．

問題一覧

　本記事で扱う問題一覧です．

• ATC001: B - Union Find
• ABC049: D - 連結 / Connectivity
• ABC075: C - Bridge
• ABC120: D - Decayed Bridges

各問題

　ネタバレ注意．

ATC001: B - Union Find

• ATC001: B - Union

　Union-Find 木の応用例として最も単純な無向グラフを扱う問題．Union-Find 木の基本的な性質を利用します．

　頂点数 N と以下に示す 2 種類のクエリが Q 回与えられます．

• 連結クエリ：頂点 A と B を繋ぐ辺を追加する．
• 判定クエリ：頂点 A と B が連結かどうかを判定して Yes，No を出力する．

　以上のクエリを Union-Find 木を使って処理します．コードを以下に示します．

// ATC001_B
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1

class UnionFind {
public:
    vector < ll > par; // 各元の親を表す配列
    vector < ll > siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N, Q, P, A, B;
    cin >> N >> Q;
    UnionFind uf(N);

    // calculation
    REP(i, Q) {
        cin >> P >> A >> B;
        if (P == 0) {
            uf.merge(A, B);
        } else {
            if (uf.issame(A, B)) cout << "Yes" << "\n";
            else cout << "No" << "\n";
        }
    }

    return 0;
}

ABC049: D - 連結 / Connectivity

• ABC049: D - 連結 / Connectivity
• editorial
• 参考：ABC049-D：連結 / Connectivity(400)

　同じ頂点を持つ UnionFind 木を 2 つ用意し uf1, uf2 とし，それぞれに対して辺を繋げるクエリを受けとり，uf1, uf2 のどちらにおいても連結な頂点はいくつかあるかを求める問題です．

　例えば，頂点 i, j が uf1, uf2 のどちらでも連結であるというのは，

uf1.root(i) == uf1.root(j) かつ uf2.root(i) == uf2.root(j)

です．各頂点 i に対してそれぞれ (i を含まない)1 ~ n の頂点 j と比較して全てのペアを全探索すると， となって間に合いません．

　Union-Find 木の重要な性質として，「頂点 i と j が連結である」＝「i と j の根（親）が同じ」というものがあります．これは単純に，根が同じであれば同じ木に属するためです．

　よって，各頂点 i について uf1 と uf2 の根をペアで保持し，同一のペアの個数を数え，

uf1.root(i) == uf1.root(j) かつ uf2.root(i) == uf2.root(j)

という条件を満たす場合の数を連想配列で管理すれば答えを求めることができます．

// VABC049_D
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define pll pair<ll, ll>

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.resize(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N, K, L, p, q;
    cin >> N >> K >> L;
    vector<ll> res(N, 1);
    UnionFind Road(N), Rail(N);
    REP(i, K) {
        cin >> p >> q; --p; --q;
        Road.merge(p, q);
    }

    REP(i, L) {
        cin >> p >> q; --p; --q;
        Rail.merge(p, q);
    }

    // 道路でも電車でも連結してる
    // 根が同じ
    map<pll, ll> mp;
    REP(i, N) mp[{Road.root(i), Rail.root(i)}]++;
    REP(i, N) cout << mp[{Road.root(i), Rail.root(i)}] << " ";
    cout << endl;

    return 0;
}

　ペアを保持するという考え方がなかなか理解できなかったので要復習です．

ABC075: C - Bridge

• ABC075: C - Bridge
• editorial

　典型的な Union-Find を使う問題．ある辺を壊した時にグラフが非連結となる辺のことを橋と言います（橋：その辺が壊すとグラフが連結でなくなってしまう辺）．この問題では，この橋の本数を求めます．この問題は Union-Find を使えば簡単に解くことができます．

　制約が小さいので，ある辺をつなげない場合の UnionFind 木 を全探索します．

// ABC075_C
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>  // std::swap()
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define pll pair<ll, ll>
#define F first
#define S second

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N, M, a, b;
    cin >> N >> M;
    vector<pll> vec(M);
    REP(i, M) {
        cin >> a >> b; --a, --b;
        vec[i].F = a;
        vec[i].S = b;
    }

    // calculation
    UnionFind uf(N);
    ll res = 0;
    REP(i, M) {
        uf.init(N);
        REP(j, M) {
            if (j == i) continue;
            uf.merge(vec[j].F, vec[j].S);
        }
        if (uf.size(0) < N) res++;
    }

    cout << res << "\n";

    return 0;
}

　この問題では，色々な解法を試すことができます．

• Union-Find 木
• DFS
• BFS
• ワーシャルフロイド法

などが使えます．ただし問題の制約によっては DFS，BFS が通用しない場合があります．

ABC120: D - Decayed Bridges

• ABC120: D - Decayed Bridges
• 参考：AtCoder ABC 120 D - Decayed Bridges (400 点)（けんちょんさんの記事）

　Union-Find を使う典型的な問題．けんちょんさん曰く，とても教育的な問題だそうです．

• UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む)
• クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする)
• 差分のみ更新する考え方

あたりを学ぶことができます．問題の要約を以下に示します．

　N 頂点 M 辺の連結な無向単純グラフが与えられる．M 辺を順番に破壊していく．i 番目に破壊する辺は a_i と b_i を結ぶ辺となっている．各 i 回目の状態において以下のクエリに答えよ: 頂点のペアであって，互いに行き来できないものを数え上げよ．

　一見，クエリに従って，

• 橋を壊す
• 繋がっているかどうかを調べる（DFS，BFS，ワーシャルフロイド法など）
• 「不便さ＝行き来できない頂点のペアの数」を求める

という操作を繰り返したいところですが，頂点数の制約が であるため上記の手法では当然間に合いません．

　計算量の問題で「辺を壊す処理」を考えるとできないので，「何もないところから辺を足していく（繋ぐ）処理」という逆の処理を考えます．「全ての橋を壊し終わった（全ての頂点が孤立している）」時点からクエリを遡っていくと，

• 全ての頂点が孤立（M 個目のクエリ（最後のクエリ）終了後）
• 1 つだけ辺がある（M-1 個目のクエリ終了後）
• 2 つだけ辺がある（M-2 個目のクエリ終了後）

...

という状態になっていることが分かります．ここで，答えである「不便さ」をクエリを遡りながら考えてみます．頂点数を N として，クエリを遡った時の辺の数を見ていくと，

• 辺が 0 本（全ての頂点が孤立している）のときの不便さ：
• 辺が 1 本（全ての頂点が孤立している）のときの不便さ：（ここでの 「-1」は新しくできたペアの分の不便さが解消されたことを表す）

...

となり，クエリを遡って頂点を繋いでいくだけで「不便さ」が簡単に求められそうです．この繋ぐ処理を Union-Find 木で実現します．

　クエリによって頂点を繋げた時に，

• 繋げる頂点の根が同じ：（現在の不便さ）はそのまま
• 繋げる頂点の根が異なる：（現在の不便さ）-（頂点 A の木のサイズ）×（頂点 B の木のサイズ）

であることに気をつけて「不便さ」を求めれば答えを求めることができます．不便さに「現在の」と付けたのは，クエリを与えるにつれて不便さが更新され，クエリが与えられる前後の差分を取る必要があるためです（差分更新の考え方）．差分を取らないと，クエリを与える度に毎回全ての頂点についてどの根に属するかを求めなければいけません．実装を以下に示します．

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;

#define REP(i, N) for (ll i = 0; i < N; ++i)
#define pll pair<ll, ll>
#define F first
#define S second

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        siz.assign(sz_, 1LL);  // assign: 再代入
        par.resize(sz_);  // resize: 再確保
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    // input
    ll N, M;
    ll node1, node2;
    cin >> N >> M;
    vector<pll> A(M);
    for (ll i = 0; i < M; i++) {
        cin >> node1 >> node2; --node1, --node2;
        A[i].F = node1;
        A[i].S = node2;
    }

    // calculation
    vector<ll> ans(M);
    ans[M-1] = (N*(N-1))/2;  // 全ての頂点が孤立している状態

    UnionFind uf(N);
    for (ll i = M-1; i >= 1; --i) {
        node1 = A[i].F, node2 = A[i].S;
        if (uf.issame(node1, node2)) {
            ans[i-1] = ans[i];
        } else {
            // 根が異なるとき，それぞれのサイズの積（頂点の組み合わせ）を引く．
            ans[i-1] = ans[i] - (uf.size(node1) * uf.size(node2));
            uf.merge(node1, node2);
        }
    }

    REP(i, M) {
        cout << ans[i] << "\n";
    }

    return 0;
}

　もう一度まとめておくと，この問題では，

• UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む)
• クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする)
• 差分のみ更新する考え方

の 3 つの考え方を学ぶことが出来ました．自分的には，それに加えて

• クエリを全て与えた後の最終状態，最終状態から一つ前（さらに前）を遡って見る

という考察のきっかけとなる知見を得ました．

類題

　類題を載せておきます．

• AISing プロコン 2019: C - Alternating Path
• 素集合データ構造（Union-Find） このページの下の方に例題が多く掲載されています．

終わりに

　拙い記事を最後まで読んでくださり本当にありがとうございます．本記事では，競プロをやっていて初めて「競プロっぽい」データ構造を実装して問題を解くということをしました．理解するのに時間がかかってしまいましたが，記事を書くことで少し Union-Find の考え方に慣れることができました．

　無駄に長い割には内容が薄めになってしまいましたが，それは理解力，言語化をする力を含めて現在の実力だと思います．分かりやすい方の記事は解説が簡潔ですっと頭に入ってきますが，私の場合そうはできませんでした．ものごとを簡潔に説明できるようになるために，これからも勉強していきたいと思います．

　本記事を書くにあたって，Twitter の FF の方々から多くのことを教えていただきました．私の競プロ生活を支えてくださっているのは間違いなく暖かい競プロのコミュニティであり，本当に感謝しております．教えていただいたことをアウトプットという形で残すことで，少しでも恩返しすることができたらなと思っている次第です．

　また，本記事は，ネットの資料を集めたものを元にまとめているため，まとまりがなく間違いがところどころあるかもしれません．間違いのご指摘，ご意見，感想等ある方はコメント，Twitter 等で連絡をいただければと思います．また，本記事の他にも競プロ覚書というタグで競プロのポイントを記事にまとめているので宜しければご覧ください．

pyteyon.hatenablog.com

pyteyon.hatenablog.com

*1:構造体等を用いずにグローバル変数，関数を使って実装することはできますが，用いて実装した方が使い回す上で便利です．

*2:C++ では union は予約語なので使えません．"U"nion と実装する方もいますが，私はなんか嫌なので merge にしました．

*3:std::vector で実装しているが配列でも当然大丈夫（むしろ余計なオーバラップが少ない？）．