Zenn
Closed11

UnionFindを自作する

#
競技プログラミング
ardririyardririy

目指すもの

競技プログラミング用の汎用UnionFindを書く

実装すること

  • marge
  • connected
  • root
  • size
ardririyardririy

一旦関数とか普通に書いてからクラスにしてみる方針で

ardririyardririy

ざっとこんな感じかな．size関数をどう実装するかと，経路圧縮をどうするかはちょっと悩みどころ

int root(vector<int> &uf, int n) {
    if (uf[n] == n) return 0;
    return root(uf, uf[n]);
}

bool connected(vector<int> &uf, int a, int b) {
    return root(uf, a) == root(uf, b);
}

void marge(vector<int> &uf, int a, int b) { uf[a] = b; }
ardririyardririy

うーんsizeの実装がびっくりするぐらい思いつかない．

愚直に調べるとO(N)かかって，これだと遅いよなぁ...

ardririyardririy

普通にBFSでとんでもない計算量になる！？とか思ってたけど，適切に経路圧縮したらO(N)で済みそう．これ以上の改善は思いつかない．

ardririyardririy

とりあえずこれでいいかな．これ以上は思いつかないや

void marge(vector<int> &uf, int a, int b) { uf[a] = root(uf, b); }

int size(vector<int> &uf, int n) {
    int cnt = 0;
    int r = root(uf, n);
    for (int k : uf)
        if (k == r) cnt++;
    return cnt;
}
ardririyardririy

色々修正して，とりあえず関数の状態まで動くやつまでできた．

int root(vector<int> &uf, int n) {
    if (uf[n] != n) uf[n] = root(uf, uf[n]);
    return uf[n];
}

bool connected(vector<int> &uf, int a, int b) {
    return root(uf, a) == root(uf, b);
}

void marge(vector<int> &uf, int a, int b) {
    int root_a = root(uf, a);
    int root_b = root(uf, b);
    if (root_a != root_b) uf[root_a] = root_b;
}

int size(vector<int> &uf, int n) {
    int cnt = 0;
    int r = root(uf, n);
    for (int k : uf)
        if (k == r) cnt++;
    return cnt;
}
ardririyardririy

Classにした．sizeも問題なく動いてそうだし，実行時間も問題なさそう(https://atcoder.jp/contests/abc304/submissions/42033592 )だったのでこれで完成にしていいかな

class UnionFind {
   private:
    vector<int> uf;

   public:
    UnionFind(int size) : uf(size) {
        for (int i = 0; i < size; i++) uf[i] = i;
    }

    int root(int n) {
        if (uf[n] != n) uf[n] = root(uf[n]);
        return uf[n];
    }

    bool connected(int a, int b) { return root(a) == root(b); }

    void marge(int a, int b) {
        int root_a = root(a);
        int root_b = root(b);
        if (root_a != root_b) uf[root_a] = root_b;
    }

    int size(int n) {
        int cnt = 0;
        int r = root(n);
        for (int k : uf)
            if (k == r) cnt++;
        return cnt;
    }
};
ardririyardririy

他の人の早いやつと比べるとちょっと遅いけど．とりあえず完成ということにしておこう

このスクラップは2023/06/06にクローズされました