C++で特定の条件を満たすグラフを構築するプログラム

2つの整数 N と K が与えられます。ここで、N 個の頂点を持つ無向グラフについて考えます。このグラフは以下の条件をすべて満たす必要があります。

• グラフは単純グラフであり、かつ連結である
• 頂点には 1 から N までの番号が付けられている
• グラフの辺の数を M とすると、辺には 1 から M までの番号が付けられており、各辺の長さは 1 です。辺 i は頂点 U[i] と頂点 V[i] を結びます
• i < j を満たす頂点のペア (i, j) のうち、2 頂点間の最短距離がちょうど 2 になるものが正確に K 組存在する

このようなグラフが存在する場合はそれを構築して出力し、存在しない場合は -1 を返します。

例として、入力が N = 5、K = 3 の場合の出力を見てみましょう。

アプローチのポイント

まず、頂点 1 を中心とするスター型グラフ(星形グラフ)を基準に考えます。頂点 1 と他のすべての頂点を辺で結ぶと、頂点 1 を含まない任意の 2 頂点間の距離は必ず 2 になります。このようなペアの総数は (N−1) × (N−2) / 2 通りです。

条件では距離 2 のペアがちょうど K 組必要なため、頂点 2 以降どうしに辺を追加して、距離 2 だったペアを距離 1 へと変えていきます。追加が必要な辺の本数は (N−1) × (N−2) / 2 − K 本です。もし K が (N−1) × (N−2) / 2 を超えている場合は、条件を満たすグラフが存在しないため -1 を出力します。

解法の手順

以下の手順に従って問題を解きます。

もし k > (n - 1) * (n - 2) / 2 ならば:
    -1 を出力
(n - 1) * (n - 2) / 2 - k + n - 1 を出力
i = 1 から n - 1 まで繰り返し:
    ペア (1, i + 1) を出力
count = (n - 1) * (n - 2) / 2 - k
i = 2 から n まで繰り返し:
    j = i + 1 から n まで繰り返し:
        もし count <= 0 ならば:
            処理を終了する
        ペア (i, j) を出力
        count を 1 減らす

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

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

void solve(int n, int k){
    if (k > (n - 1) * (n - 2) / 2){
        cout << -1 << endl;
    }
    cout << (n - 1) * (n - 2) / 2 - k + n - 1 << '\n';
    for (int i = 1; i < n; i++){
        cout << 1 << ", " << i + 1 << '\n';
    }
    int count = (n - 1) * (n - 2) / 2 - k;
    for (int i = 2; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (count <= 0){
                return;
            }
            cout << i << ", " << j << '\n';
            count--;
        }
    }
}
int main(){
    int N = 5;
    int K = 3;
    solve(N, K);
}

入力

5, 3

出力

7
1, 2
1, 3
1, 4
1, 5
2, 3
2, 4
2, 5

出力の最初の行は辺の総数(M = 7)を示しており、続く行が実際の辺の一覧を表しています。頂点 1 を中心としたスター構造に、頂点 2・3・4・5 間の辺を 3 本追加することで、距離 2 のペアがちょうど K = 3 組になるグラフが構築できていることが分かります。