AtCoder ABC #131 E - Friendships

E - Friendships

問題

N頂点単純連結無向グラフで最短距離が2である頂点対がK個あるものを構築する。

解説

まず最短距離が2である頂点対が最大となるのはある１点（仮に「中心点」と呼ぶ）が他の全ての点と辺を持ち、それ以外の辺が存在しないときである。

このとき頂点対の数はである。したがってKがこれより大きい場合は構築不可である。

そして中心点以外の頂点を辺でつなぐとその頂点対のみ最短距離は1となって最短距離が2の辺数を1だけ減らすことができる。

コードは以下のようになる

fn solve(n: u64, k: u64) -> Option<Vec<(u64, u64)>> {
    if k > (n - 1) * (n - 2) / 2 {
        return None;
    }

    let mut ans = (2..(n + 1)).map(|i| (1, i)).collect::<Vec<(u64, u64)>>();

    let times = (n - 1) * (n - 2) / 2 - k;
    let mut cnt = 0;
    let mut s = 2;
    let mut e = 3;

    while cnt < times {
        ans.push((s, e));
        if e == n {
            s += 1;
            e = s + 1;
        } else {
            e += 1;
        }
        cnt += 1;
    }

    Some(ans)
}