JOI 春合宿 2007 day4-1 Fiber (難易度 5)

無向グラフの連結成分の個数を数える問題

• ジャッジへのリンク
• 問題へのリンク

問題概要

頂点数 、辺数 の無向グラフが与えられる。このグラフにいくつかの辺を新たに追加することによって、グラフ全体が連結となるようにしたい。

追加すべき辺の本数の最小値を求めよ。

制約

• 
• 

考えたこと

グラフの連結成分の個数を求めて、1 を引けばよい。グラフの連結成分の個数を求めるのは

• Union-Find を使う
• DFS する
• BFS する

などの方法がある。どれでやっても解ける。以下の実装では Union-Find を用いた。

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

struct UnionFind {
    vector<int> par;

    UnionFind() { }
    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 u, v; cin >> u >> v; --u, --v;
        uf.merge(u, v);
    }
    int res = 0;
    for (int i = 0; i < N; ++i) if (uf.root(i) == i) ++res;
    cout << res-1 << endl;
}