ABC177のD問題に挑戦してみた - インフラエンジニアの備忘録とか色々

初めに

今回はABC177のD問題に挑戦してみました。
この問題は、Union-findというデータ構造を使用すると簡単に解ける問題で、
今まで書いた事が無いアルゴリズムだったので、今回はABC177のD問題について書きます。

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

https://atcoder.jp/contests/abc177/tasks/abc177_d

人1から人NまでのN人がおり、それぞれの人の友人関係情報が入力されます。
N人をいくつかのグループに分ける際に、すべての人について友人が同じグループにいない状態
にするには最小でいくつのグループに分ければ良いかを求める問題です。

回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

struct UnionFind {

vector<int> d;

UnionFind(int N){
    //初期化
    d = vector<int>(N,-1);
}

int find(int x){
    //根に到達したら根の値を返す
    if(d[x] < 0) return x;
    //同じ根に属する要素の
    return d[x] = find(d[x]);
}

bool unite(int x,int y){

    //xとyに結合する根の情報を格納
    x = find(x);y = find(y);

    //根が同じであれば、結合処理は不要
    if(x == y) return false;

    //xの方がyより根が大きければxとyの値を入替
    if(d[x] > d[y]) swap(x,y);

    //連結する根(y)のサイズを新たな根(x)に加算
    d[x]+=d[y];

    //yの新しい根としてxを設定
    d[y]=x;

    return true;

}

//同じ根に属しているか判定
bool same(int x,int y){
  return find(x) == find(y);
}
//連結成分のサイズ返す
int size(int x){
  return -d[find(x)];
}
};

int main(){

    ll N,M;
    ll A,B;

    cin >> N >> M;
    UnionFind UF(N);

    for(ll i = 0;i < M;++i){
        cin >> A >> B;
        --A;--B;
        UF.unite(A,B);
    }

    int ans = -1;

    for(int i = 0;i < N;++i){
      ans = max(ans,UF.size(i));
    }
  
    cout << ans << endl;

    return 0;
}

この問題は、Union-Findというデータ構造を利用すると簡単に解くことが出来ますので、
まずはUnion-Findについて記載した後に問題を解いていこうと思います。

Union-Findは下記のような共通部分を持たない集合を保持することが出来るデータ構造です。

f:id:hgm_blog:20201230230115p:plain

Union-Findは、主に以下の操作を行う事で素集合の保持と
ある要素がどの集合に属するか判定を行う事が出来ます。

　Unite：同様な根を持つ2つの集合を結合する操作
　Find：要素が属している集合の根を見つける操作

※詳細については下記ブログに情報がまとめられていたので、こちらを参照下さい。
pyteyon.hatenablog.com Union-Find Tree を理解する！素集合系を扱うデータ構造 | アルゴリズムロジック

Uniteは以下のような操作になります。根となっている配列には集合のサイズを格納しています。
(正負が逆転しているので注意。プログラムと一緒に見てみて下さい。)

f:id:hgm_blog:20201231140026p:plain

Findは以下のような操作になります。
(プログラム上ではreturnする時に集合に属する要素の結合先を根の値に縮約しています。)

f:id:hgm_blog:20201231114446p:plain

※配列の添え字は0基算で記載しています。

上記のようなイメージでUniteとFindの操作は行われます。

Union-Findがわかると問題を解くのは簡単です。N人の人をそれぞれ友達がいないグループに分ける場合、グループの数を最小とするには、一番大きい集合の要素数と同じ数のグループが必要となります。
(一番大きい集合の要素数より小さいグループ数とすると少なくとも1つは友達関係持つ人がグループになります。)

そのため、プログラム中で求めている各集合のサイズが最大のものを求めて出力することで答えを求める事が出来ます。

最後に

久しぶりにブログ書きましたがやはりまとめると理解が深まりますね。
ただ、Union-Findは他にも書き方があったりとまだ完全に理解して使いこなせる訳ではないので
精進しようと思います。(Union-Findはより理解が深まったら書き直すかもです。)
あと少しで目標の茶色になりそうなので頑張ります！（あと60あげればいける！）

Appendix:Union by rank

Union-Findはいくつかの書き方があるようで、上述したものはUnion by Sizeという書き方です。
もう一つUnion by rankという書き方があるようで以下にその書き方の備忘を記載しています。
※そのうち加筆します。

vector<int> d;
vector<int> rank;

UnionFind(int N){
    //初期化
    for(int i = 0;i < N;++i) d[x] = x;
    rank = vector<int>(N,0);
}

int find(int x) {
    if (x == d[x]) return x;
    return d[x] = find(d[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    //xのrankの方が大きい場合はyの接続先をxに付け替える
    if (rank[x] > rank[y]) { 
        d[y] = x;
    //上記条件を満たさない場合はxの接続先をyに付け替える
    } else {
        d[x] = y;
        // rankが同じ場合はrankの値を1つ増やす
        if (rank[x] == rank[y]) {
            rank[y]++;
        }
    }
}

Union by rankの書き方で結合する場合は以下のようになります。

f:id:hgm_blog:20210101151725p:plain