Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける

問題概要

頂点数 $N$ 、辺数 $M$ の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。

制約

$N, M \le 10^{5}$

考えたこと

全体が連結ならば 0 本となる。

連結成分が 2 個ならば 1 本の辺によって全体を連結にできる
連結成分が 3 個ならば 2 本の辺によって全体を連結にできる

一般に、連結成分が $K$ 個ならば、 $K-1$ 本の辺によって全体を連結にできる。

逆に、辺を 1 本追加することによって、連結成分の個数を 2 以上減らすことはできない。よって連結成分が $K$ 個あるならば、 $K-1$ 本以上の辺はかならず必要になる。

以上から、

連結成分の個数を求めて
そこから 1 を引く

という方法で求められることがわかった。

解法 (1)：Union-Find

連結成分といえばグループ。グループといえば Union-Find。Union-Find によって連結成分のグループ分けを効率よく行うことができる。具体的には各辺 $(u, v)$ に対して、

uf.merge(u, v);

という処理を行っていけばよい。そして最後にグループの個数を数える場面では次のようにする。

Union-Find の各グループは根付き木となっている
よって、Union-Find の要素のうち、「根」となっているものの個数を求めればよい
Union-Find 中の要素 v が根かどうかは、uf.root(v) == v が true かどうかによって判定することができる

以上に基づいて次のように実装できる。計算量は $O((N + M) \alpha(N) )$ 。

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        uf.merge(a, b);
    }
    int res = 0;
    for (int i = 0; i < N; ++i) if (uf.root(i) == i) ++res;
     cout << res - 1 << endl;
}

解法 (2)：DFS

グラフ探索解法に基づく解法もある。DFS とは、

グラフ上の一点 v を始点として
それに繋がる点を再帰的に呼び出していく

というものである。よって、各連結成分に対して、その中の 1 点 v に対して再帰関数 dfs(v) を呼び出すと、v を含む連結成分内の頂点をすべて訪問することになる。

以上の考察に基づくと、次のような実装によって、連結成分の個数を数えることができる。

int counter = 0;
vector<bool> seen(N, false);
for (int v = 0; v < N; ++v) {
  if (seen[v]) continue;
  dfs(v);
  ++counter;
}

つまり、すべての頂点が探索済みとなるまで探索を繰り返す。dfs(v) が呼ばれるときは、毎回「新たな連結成分内の頂点 v」が呼び出されていることになる。よって dfs(v) を呼び出すタイミングで counter をインクリメントすれば、counter の値が求める連結成分数となる。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void dfs(const Graph &G, vector<bool> &seen, int v) {
    seen[v] = true;
    for (auto nv : G[v]) if (!seen[nv]) dfs(G, seen, nv);
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int res = 0;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        dfs(G, seen, v);
        ++res;
    }
    cout << res - 1 << endl;
}

解法 (3)：BFS

DFS による解法とまったく同じ考え方で、BFS によっても解ける。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void bfs(const Graph &G, vector<int> &dist, int s) {
    dist[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (dist[nv] == -1) {
                dist[nv] = dist[v] + 1;
                que.push(nv);
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int res = 0;
    vector<int> dist(N, -1);
    for (int v = 0; v < N; ++v) {
        if (dist[v] != -1) continue;
        bfs(G, dist, v);
        ++res;
    }
    cout << res - 1 << endl;
}