C++で無向グラフ内のすべてのサイクルの長さの積を求める方法

本記事では、無向かつ非重み付きグラフが入力として与えられたとき、そのグラフ内に形成されるすべてのサイクルの長さ（頂点数）の積を求め、結果を出力する方法を解説します。

具体例

入力例1

この図では合計8つのノードがあり、そのうちノード1、6、3、5、8の5つがサイクルを形成しています。残りのノードはサイクルに含まれません。したがって、サイクルの長さは5であり、積は5となります。

入力例2

この図では合計12のノードがあり、そのうち11個（5個＋6個）のノードが2つのサイクルを形成しています。1つ目はノード1、6、3、5、8からなるサイクル、2つ目はノード9、4、10、11、22、12からなるサイクルです。残りのノード2はどちらのサイクルにも含まれません。したがって、求める積は 5 × 6 = 30 となります。

プログラムで使用するアプローチ

• サイクルを形成するノードを入力として受け取る
• DFS（深さ優先探索）関数を作成し、ノードに色を付けながら頂点を走査する
• 各ノードは「完全に訪問済み」または「部分的に訪問中」のいずれかの状態を持つ
• 完全に訪問済みのノードは再訪問不要のため保存せず、部分的に訪問中のノードは再度訪問される可能性があるため保存する
• 最終的な結果を出力する

アルゴリズム

開始
ステップ1 → DFSを用いてグラフを走査する関数を宣言
    void DFS(int i, int j, int color[], int highlight[], int parent[], int& number)
    IF color[i] = 2 （完全訪問済みの場合）
        Return
    End
    IF color[i] = 1 （訪問中の場合＝閉路を検出）
        number++
        int temp = j を宣言・設定
        highlight[temp] = number を設定
        Loop While temp != i
            temp = parent[temp]
            highlight[temp] = number
        End
        Return
    End
    parent[i] = j を設定
    color[i] = 1 を設定
    For int k : graph[i]
        IF k = parent[i]
            Continue
        End
        DFS(k, i, color, highlight, parent, number) を呼び出す
    End
    color[i] = 2 を設定
ステップ2 → サイクル内ノード数の積を求める関数を宣言
    int product(int edge, int highlight[], int& number)
    unordered_map<int, int> mp を宣言
    Loop For i = 1 ～ i <= edge
        IF highlight[i] != 0
            mp[highlight[i]]++
        End
    End
    int temp = 1 を宣言・設定
    Loop For i = 1 ～ i <= number
        temp = temp * mp[i]
    End
    IF number = 0
        temp = 0 を設定
    End
    return temp
ステップ3 → main() 内での処理
    insert(1, 2) などの関数呼び出しでノードを挿入
    int color[size], parent[size] を宣言
    int highlight[size] を宣言
    int number = 0 を宣言・設定
    int edge = 10 を宣言・設定
    DFS(1, 0, color, highlight, parent, number) を呼び出す
    product(edge, highlight, number) を呼び出して結果を出力
終了

C++実装コード

#include <bits/stdc++.h>
using namespace std;
const int size = 100000;
vector<int> graph[size];
// DFSを用いてグラフを走査する関数
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) {
    // 完全に訪問済みのノードの場合
    if (color[i] == 2) {
        return;
    }
    // 訪問中のノードの場合（閉路を検出）
    if (color[i] == 1) {
        number++;
        int temp = j;
        highlight[temp] = number;
        // 頂点をバックトラックして閉路全体にマークを付ける
        while (temp != i) {
            temp = parent[temp];
            highlight[temp] = number;
        }
        return;
    }
    parent[i] = j;
    color[i] = 1;
    for (int k : graph[i]) {
        if (k == parent[i]) {
            continue;
        }
        DFS(k, i, color, highlight, parent, number);
    }
    color[i] = 2;
}
// グラフに辺を挿入する関数
void insert(int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}
// 閉路内のノード数の積を求める関数
int product(int edge, int highlight[], int& number) {
    unordered_map<int, int> mp;
    for (int i = 1; i <= edge; i++) {
        if (highlight[i] != 0)
        mp[highlight[i]]++;
    }
    int temp = 1;
    for (int i = 1; i <= number; i++) {
        temp = temp * mp[i];
    }
    if (number == 0)
    temp = 0;
    return temp;
}
int main() {
    // グラフにノード（辺）を挿入
    insert(1, 2);
    insert(2, 3);
    insert(3, 4);
    insert(4, 6);
    insert(4, 7);
    insert(5, 6);
    insert(3, 5);
    insert(7, 8);
    insert(6, 10);
    insert(5, 9);
    insert(10, 11);
    int color[size], parent[size];
    int highlight[size];
    int number = 0;
    int edge = 10;
    DFS(1, 0, color, highlight, parent, number);
    // 閉路の積を出力する関数
    cout<<"閉路内のすべてのノード数の積 :"<< product(edge, highlight, number);
    return 0;
}

出力結果

Product of all the nodes in the cycle is :4

解説のポイント

このアルゴリズムでは、色分けによるDFSを活用しています。color配列の値は以下の状態を表します。

• 0（未訪問）：まだ一度も訪問していないノード
• 1（訪問中）：現在の探索パス上にあるノード。ここに再び到達すると閉路が検出されたことを意味します
• 2（完全訪問済み）：探索が完了したノード。再訪問は不要です

閉路が検出されると、parent配列を使ってバックトラックしながら閉路を構成するノードすべてに同じ番号（number）をマークします。その後、product関数がマークごとのノード数を集計し、各閉路の長さの積を計算します。計算量はDFSの O(V + E) に加えて集計処理が加わるため、大規模なグラフに対しても効率的に動作します。