C++で無向グラフの連結成分の数を求める方法（DFSによる実装解説）

本記事では、C++を用いて無向グラフの連結成分（Connected Components）の数を求めるアルゴリズムについて解説します。

問題の概要

0 から n-1 までのラベルが付いた n 個のノードと、無向エッジのリストが与えられたとき、グラフ内に存在する連結成分の数を返す関数を実装します。

例として、入力が次の場合を考えてみましょう。

• n = 5
• edges = [[0, 1], [1, 2], [3, 4]]

この場合、ノード {0, 1, 2} がひとつのグループを形成し、{3, 4} がもうひとつのグループを形成するため、出力は 2 となります。

解決アプローチ：深さ優先探索（DFS）

この問題は、DFS（深さ優先探索）を使うことで効率的に解けます。基本的な考え方は以下の通りです。

1. 訪問済みかどうかを記録する配列 visited を用意する。
2. まだ訪問していないノードを見つけたら、そこから DFS を開始し、到達可能なすべてのノードを訪問済みにする。
3. DFS の開始回数をカウントすれば、それが連結成分の数になる。

アルゴリズムの手順

1. 関数 dfs(node, graph, visited) を定義する。
   • visited[node] が false の場合は true に設定する。
   • graph[node] に含まれる各隣接ノードに対して再帰的に dfs() を呼び出す。
2. メイン処理では以下を行う。
   • サイズ n の配列 visited を定義する。
   • n が 0 の場合は 0 を返す。
   • 隣接リスト形式のグラフ graph[n] を構築する。各エッジ [u, v] について、graph[u] に v を、graph[v] に u を追加する（無向グラフのため双方向に登録）。
3. カウンタ ret を 0 で初期化する。
4. i = 0 から n-1 までループし、visited[i] が false のノードに対して dfs(i, graph, visited) を呼び出し、ret を 1 増やす。
5. ret を返す。

C++での実装例

以下に実際のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    void dfs(int node, vector<int> graph[], vector<bool>& visited){
        if(visited[node]) return;
        visited[node] = true;
        for(int i = 0; i < graph[node].size(); i++){
            dfs(graph[node][i], graph, visited);
        }
    }
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<bool> visited(n);
        if(!n) return 0;
        vector<int> graph[n];
        for(int i = 0; i < edges.size(); i++){
            int u = edges[i][0];
            int v = edges[i][1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        int ret = 0;
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                dfs(i, graph, visited);
                ret++;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1},{1,2},{3,4}};
    cout << (ob.countComponents(5, v));
}

入力

5, [[0,1],[1,2],[3,4]]

出力

2

計算量について

• 時間計算量： O(n + E) ― 各ノードと各エッジをそれぞれ高々1回ずつ処理するためです（E はエッジ数）。
• 空間計算量： O(n + E) ― 隣接リストと訪問管理用の配列が必要になります。

まとめ

無向グラフの連結成分の数を求める問題は、DFS を使って未訪問のノードから到達可能な範囲をすべてマークしていき、その開始回数を数えるだけで解決できます。同様のアプローチは Union-Find（素集合データ構造）でも実装可能なので、興味があれば比較してみると理解が深まります。