問題概要

頂点数 $N$ 、辺数 $M$ の単純な無向グラフが与えられる。

このグラフの連結成分の個数を求めよ。

制約

$1 \le N \le 100$
$0 \le M \le \frac{N(N-1)}{2}$

解法

まず、単純グラフや連結成分という概念についてはこちら！

algo-method.com

グラフの入出力の扱い方についても、このページで解説しています。

algo-method.com

グラフの連結成分の個数を求めるためには、次の 3 つの方法が代表的です。

DFS
BFS
Union-Find

DFS と BFS については、次の記事群で解説しています。

Union-Find については、まずは ACL (AtCoder Library) を活用してみるのもアリだと思います！

解答例 1：DFS

計算量は $O(N + M)$ となります。

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

// グラフ
using Graph = vector<vector<int>>;

// 頂点 v を始点とする DFS
// seen[v] := 頂点 v が探索済みならば true / そうでなければ false
void dfs(const Graph &G, int v, vector<bool> &seen) {
    // 頂点 v を探索済みにする
    seen[v] = true;
    
    // 頂点 v に隣接する各頂点 v2 を順に探索する
    for (auto v2 : G[v]) {
        // 頂点 v2 が探索済みならばスキップ
        if (seen[v2]) continue;
        
        // 再帰的に探索
        dfs(G, v2, seen);
    }
}

int main() {
    // 入力受け取り
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    // DFS
    int res = 0;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        // 頂点 v を含む連結成分がすでに探索済みの場合はスキップ
        if (seen[v]) continue;
        
        // 頂点 v を始点とする DFS を行う
        // このとき、頂点 v を含む連結成分の全体を探索することとなる
        ++res;
        dfs(G, v, seen);
    }
    cout << res << endl;
}

解答例 2：BFS

計算量は $O(N + M)$ となります。

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

// グラフ
using Graph = vector<vector<int>>;

// 頂点 s を始点とした BFS
void bfs(const Graph &G, int s, vector<int> &dist) {
    // 初期条件
    queue<int> que;
    dist[s] = 0;
    que.push(s);
    
    // BFS
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        
        for (auto v2 : G[v]) {
            if (dist[v2] != -1) continue;
            dist[v2] = dist[v] + 1;
            que.push(v2);
        }
    }
}

int main() {
    // 入力受け取り
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    int res = 0;
    vector<int> dist(N, -1);
    for (int v = 0; v < N; ++v) {
        if (dist[v] != -1) continue;
        
        // 頂点 v を始点とした BFS を行う
        ++res;
        bfs(G, v, dist);
    }
    cout << res << endl;
}

解答例 3：Union-Find

ACL の dsu を使います。計算量は $O(N + M\alpha(N))$ となります。

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

int main() {
    int N, M;
    cin >> N >> M;
    
    // ノード数が N の Union-Find 構築
    dsu uf(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        
        // 頂点 u, v を含むグループを併合する
        uf.merge(u, v);
    }
    
    // root(v) が v 自身である頂点 (各グループの根付き木の根) を数えれば良い
    int res = 0;
    for (int v = 0; v < N; ++v) {
        if (uf.leader(v) == v) ++res;
    }
    cout << res << endl;
}