ABC131 E問題：Friendships - 忘れても大丈夫

問題. Friendships

非負整数 $n, k$ が与えられたとき次を満たすグラフを構成せよ．ただし，そのようなグラフが存在しない場合は "-1" を出力せよ．

頂点数 $n$ の単純連結無向グラフ
辺重みは 1
最短距離が 2 である頂点対 $(u, v) \, (u < v)$ の数がちょうど $k$ 個

制約： $2 \le n \le 100$ ，　 $0 \le k \le \frac{n (n - 1)}{2}$

解法

頂点数 $n$ の完全グラフ $K_n$ を考えると， $K_n$ のどの 2 頂点間の最短距離も 1 であることが分かる．したがって， $k = 0$ の場合は完全グラフとして答えが存在する．

各頂点には $1, 2, \ldots, n$ と番号が付けられているとする． $K_n$ から辺 $\{u, v\} \, (u \neq 1, u < v)$ を取り除くと， $u$ と $v$ の間の最短距離が 2 となり，他の頂点対の最短距離は 1 のままであることが分かる．したがって， $k = 1$ の場合のグラフが構成できた．
このように，頂点 1 以外の頂点対を取り除くと，その間の最短距離は頂点 1 を経由する道が存在するので 2 となり，それ以外の頂点対の最短距離には影響を与えない．このようにして， $k = 0, 1, 2, \ldots$ とグラフを構成することができる．
このとき， $k$ の上限を考える．上のように頂点 1 を含まない頂点対を 1 個ずつ取り除いて，最短距離が 2 である頂点対の数を 1 個ずつ増やすグラフを構成したとき，完全グラフから頂点 1 以外の頂点対をすべて削除したスター（スター (グラフ理論) - Wikipedia）と呼ばれるグラフまでこの操作が行えることが分かる．また，スターは木なのでどの辺を削除しても非連結となる．したがって， $k$ の上限は $\frac{n (n - 1)}{2} - (n - 1) = \frac{(n - 1) (n - 2)}{2}$ となる（正確には連結性から $k < \frac{n (n - 1)}{2} - (n - 2)$ ）．

計算時間： $O(n^2)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

bool exitFriendships() {
    int n, k;
    cin >> n >> k;

    if (((n - 1) * (n - 2) / 2) < k) return false;

    int m = n * (n - 1) / 2;
    vector<vector<bool>> adj(n, vector<bool>(n, true));
    for (int v = 1; 0 < k && v < n; ++v) {
        for (int u = 1; 0 < k && u < n; ++u) {
            if (v != u && adj[v][u]) {
                --k; --m;
                adj[v][u] = adj[u][v] = false;
            }
        }
    }

    cout << m << endl;
    for (int v = 0; v < n; ++v)
        for (int u = v + 1; u < n; ++u)
            if (adj[v][u]) cout << v + 1 << " " << u + 1 << '\n';

    return true;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    if (!exitFriendships()) cout << "-1\n";

    return 0;
}

考察時間が長かったのが反省