グラフ理論：K値の最大化問題 - 二分探索とシミュレーションによる解法
問題文
n個の頂点とm辺の単純無向グラフが与えられます。このグラフを完全グラフに補完する必要があります。補完のルールは、あらかじめパラメータKを選び、各ステップで「頂点uとvの間に辺が存在せず、かつ両頂点の次数の和がK以上」である辺のみを追加することです。このルールに従って辺を追加し続けて、最終的に完全グラフに到達できるようなKを「合法なK」と呼びます。最大の合法なKを求めてください。
入力形式
第一行：二つの整数n, m（頂点数、辺数）
続くm行：各行に二つの整数u, v（無向辺を表す）
出力形式
一行に一つの整数：最大の合法なK
入力例
4 3 1 2 2 3 3 4
出力例
3
解法の考え方
核心的な観察
合法なKの値は単調性を持ちます：K=xが合法であれば、すべてx以下のKも合法です（より低いKは次数の和の条件をより満足しやすいため）。したがって、二分探索を用いて最大の合法なKを効率的に見つけることができます。
二分探索の範囲
最小の可能性：1（任意のグラフは段階的に辺を追加して補完できるため、K=1は常に合法）
最大の可能性：2n-2（完全グラフでは各頂点の次数はn-1であり、任意の2頂点の次数の和は2n-2です。初期グラフのKはこの値を超えることはありません）
Check関数：Kの合法性を検証
与えられたKについて、辺の追加プロセスをシミュレーションし、完全グラフに補完できるかどうかを判断します。核心的なロジックは以下の通りです：
- 非隣接辺の収集：初期状態で存在しないすべての辺を記録し、各辺の「重み」をその両端点の初期次数の和で初期化します（重みは現在の端点次数の和を表し、この辺が追加できるかどうかを決定します）。
- 辺の追加を繰り返す：
- すべての未追加の辺を走査し、ある辺の重みがK以上であれば、「追加済み」とマークします。
- 辺を追加した後、両端点の次数はそれぞれ1増加するため、これらの端点に関連するすべての未追加辺の重みを1増やす必要があります（これらの辺の端点次数の和が変化したため）。
- 終了条件：
- すべての非隣接辺が追加された場合（完全グラフに補完された場合）、trueを返します。
- 1回の走査で追加できる辺がなく、未追加の辺が残っている場合、falseを返します。
コードの解説
変数の定義
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
bool adj[505][505]; // 隣接行列：adj[u][v]=trueは辺の存在を示す
int degree[505]; // degree[u]：頂点uの初期次数
vector<int> vertex_edges[505]; // vertex_edges[u]：頂点uに関連する非隣接辺のインデックスリスト
struct Edge { // 非隣接辺の情報を格納
int u, v; // 辺の両端点
int weight; // 現在の端点次数の和（重み）
bool added; // 追加済みかどうか
};
vector<Edge> non_adjacent_edges; // すべての非隣接辺を格納Check関数の実装
bool check(int K) {
int total_edges = 0; // 非隣接辺の総数
non_adjacent_edges.clear();
for (int i = 1; i <= n; i++) {
vertex_edges[i].clear();
}
// 初期化：非隣接辺を収集
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (!adj[i][j]) { // 非隣接辺
total_edges++;
Edge e;
e.u = i;
e.v = j;
e.weight = degree[i] + degree[j]; // 初期重み = 初期次数の和
e.added = false;
non_adjacent_edges.push_back(e);
// 頂点iとjがこの辺に関連していることを記録
vertex_edges[i].push_back(total_edges - 1);
vertex_edges[j].push_back(total_edges - 1);
}
}
}
while (true) {
int added_count = 0; // このラウンドで追加した辺の数
int total_added = 0; // 累計追加した辺の数
// 現在追加済みの辺をカウント
for (int i = 0; i < total_edges; i++) {
if (non_adjacent_edges[i].added) total_added++;
}
if (total_added == total_edges) return true; // すべての辺が追加された場合、Kは合法
// すべての非隣接辺を走査し、追加を試みる
for (int i = 0; i < total_edges; i++) {
if (non_adjacent_edges[i].added) continue;
if (non_adjacent_edges[i].weight >= K) {
// 追加済みとマーク
non_adjacent_edges[i].added = true;
added_count++;
int u = non_adjacent_edges[i].u;
int v = non_adjacent_edges[i].v;
// uに関連するすべての非隣接辺の重みを更新（uの次数が1増えたため）
for (int edge_idx : vertex_edges[u]) {
if (!non_adjacent_edges[edge_idx].added) {
non_adjacent_edges[edge_idx].weight++;
}
}
// vに関連するすべての非隣接辺の重みを更新（vの次数が1増えたため）
for (int edge_idx : vertex_edges[v]) {
if (!non_adjacent_edges[edge_idx].added) {
non_adjacent_edges[edge_idx].weight++;
}
}
}
}
if (added_count == 0) return false; // このラウンドで辺を追加できなかった場合、Kは非合法
}
}メイン関数：二分探索による解法
int main() {
// 入力処理
cin >> n >> m;
memset(adj, false, sizeof(adj));
memset(degree, 0, sizeof(degree));
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u][v] = true;
adj[v][u] = true;
degree[u]++; // 頂点uの次数を1増やす
degree[v]++; // 頂点vの次数を1増やす
}
// 二分探索：最大可能値から下に探す（標準的二分探索に変更可能）
for (int K = 2 * n; K >= 1; K--) { // Kの最大値は2n-2、ここでは2nで十分
if (check(K)) {
cout << K << endl;
return 0;
}
}
return 0;
}入力例による検証
入力例を例にとります：
初期グラフ：4つの頂点、辺(1-2, 2-3, 3-4)
初期次数：degree[1]=1, degree[2]=2, degree[3]=2, degree[4]=1
非隣接辺：(1-3, 1-4, 2-4)、初期重みはそれぞれ1+2=3、1+1=2、2+1=3
K=3の場合：
- 第一走査：
- 辺(1-3)の重み=3≥3、追加；1と3に関連する辺の重みを更新：
- 1に関連する辺：(1-4)の重みが2+1=3に、(1-3)は追加済み
- 3に関連する辺：(2-4)の重みが3+1=4に、(1-3)は追加済み
- 辺(2-4)の重み=3≥3、追加；2と4に関連する辺の重みを更新：
- 2に関連する辺：他の未追加辺なし
- 4に関連する辺：(1-4)の重みが3+1=4
- 辺(1-4)の重み=4≥3、追加
- すべての辺が追加されたため、trueを返し、K=3は合法である。
時間計算量の分析
二分回数：O(n)（2nから1へ降順探索、または標準的二分探索でO(log n)）
各Check：
- 非隣接辺の収集：O(n²)
- 辺の追加を繰り返す：最大O(n²)回（各辺は1回だけ追加）、各走査で辺をO(n²)走査、重み更新O(n)（各頂点に関連する辺は最大O(n)本）
総計算量：O(n³)、n=500の場合、500³=125e6であり、すべてのテストケースを通過できます。
最適化の方向性
- 二分方式：「大きい値から小さい値へ」の探索を標準的二分探索（l=1, r=2n-2）に変更し、二分回数をO(log n)に削減。
- 辺のソート：Check関数内で重みの大きい順に辺を走査し、無効な走査を削減（重みの高い辺を優先的に追加することで、後続の重み更新をより早く引き起こす）。
- 配列の最適化：固定サイズの配列の代わりに動的配列（vectorなど）を使用し、メモリの浪費を削減。
まとめ
この問題の核心は、二分探索を用いてKの範囲を絞り込み、辺の追加プロセスをシミュレーションして合法性を検証することにあります。「辺を追加した後に関連する辺の重みを更新する」というロジックを理解することが重要です——端点の次数の変化は、後続の辺の追加条件に直接影響します。この「二分探索+シミュレーション」のアプローチは、グラフ理論の可解性問題でよく見られ、同様のシナリオに柔軟に適用できます。