C++でグラフの順列における最大値を求めるアルゴリズム

問題概要

この問題では、N個のノードからなるグラフが与えられます。私たちのタスクは、変更後の配列の最小値として考えられる最大値を見つけることです。

グラフに対してはノードの順列を考えます。この順列は、各ノードの左側に少なくとも1つ、共通の辺（エッジ）を共有するノードが存在するという条件のもとで、誘導される部分グラフの数に対応します。

具体例で問題を確認してみましょう。

入力 : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
出力 : 3

この例では、4つのノードが環状につながっているため、全体が1つの連結成分となり、答えは「連結成分のサイズ − 1 = 3」となります。

解法アプローチ

この問題のシンプルな解き方は、あるノードを起点として深さ優先探索（DFS）を行い、隣接するすべてのノードを訪問することです。これにより、各連結成分のサイズを求めることができます。

そして、次の式を使ってノードの順列の最大値を計算します。

連結成分のサイズ − 1

すべての連結成分についてこの値を合計したものが、最終的な答えになります。DFSを使うことで、各ノードと各辺を一度ずつ処理すればよいため、計算量は O(N + E)（Nはノード数、Eは辺数）と非常に効率的です。

実装例

以下は、上記の解法の動作を示すC++プログラムです。

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

int dfs(int x, vector<int> adjMat[], int visited[]){
    int sz = 1;
    visited[x] = 1;
    for (auto ch : adjMat[x])
        if (!visited[ch])
            sz += dfs(ch, adjMat, visited);
    return sz;
}
int maxValPermutationGraph(int n, vector<int> adjMat[]){
    int val = 0;
    int visited[n + 1] = { 0 };
    for (int i = 1; i <= n; i++)
        if (!visited[i])
            val += dfs(i, adjMat, visited) - 1;
    return val;
}
int main(){
    int n = 4;
    vector<int> adjMat[n + 1] = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};
    cout<<"グラフの順列の最大値は "<<maxValPermutationGraph(n, adjMat);
    return 0;
}

出力結果

グラフの順列の最大値は 3

まとめ

この記事では、グラフの連結成分ごとにDFSを実行し、「連結成分のサイズ − 1」を合計することで、順列における最大値を効率的に求める方法を紹介しました。訪問済みフラグを管理しながら未訪問のノードを起点に探索を開始するのがポイントです。