Codeforces Round #527 Div.3 E: Minimal Diameter Forest

問題概要

$N$ 頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。

解説

森を木に分割して、木同士をマージすることを考えます。木 $T_1$ と $T_2$ をマージする際にどの頂点を選択するかが問題ですが、これは木 $T_1$ の中心 $c_1$ と木 $T_2$ の中心 $c_2$ の間を接続するのが最適です。木 $T_1$ の直径を $D_1$ と、中心からの距離最大値 (つまり半径) を $d_1$ とします。 $T_2$ についても同様に $D_2, d_2$ を定義します。このように接続することで、マージされた後の木の直径は $\max \left( D_1, D_2, d_1 + d_2 + 1 \right)$ となります。

中心同士を順に接続していくことになりますが、中心の頂点のみからなるグラフはどのような形をしていればよいでしょうか？直径を最小化するには、スターグラフにように接続することが最適です。また、元の木において直径が最大になるものをスターグラフ中の次数が多くなる頂点に割り当てることで、最適なマージが可能になります。

ソースコード

vector<int> G[1010];
int N, M, used[1010];

void dfs(int cur, vector<int> &dist) {
    for(auto to : G[cur]) {
        if(dist[to] >= 0) continue;
        dist[to] = dist[cur] + 1;
        dfs(to, dist);
    }
}

pair<int, int> get_graph_info(int id) {
    vector<int> d0(N, -1), d1(N, -1), d2(N, -1);
    d0[id] = 0; dfs(id, d0);

    // 直径は p1 と p2 をつなぐパスになる
    int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
    d1[p1] = 0; dfs(p1, d1); // d1 は p1 からの距離を記憶したもの
    int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
    d2[p2] = 0; dfs(p2, d2); // d2 は p2 からの距離を記憶したもの
    int diam = d2[p1];

    int mi = INF, res = -1;
    for(int i=0; i<N; i++) {
        if(d1[i] < 0 or d2[i] < 0) continue;
        used[i] = true;
        int tmp = max(d1[i], d2[i]);
        if(mi > tmp) mi = tmp, res = i;
    }
    return make_pair(diam, res);
}

signed main() {
    scanf("%lld%lld", &N, &M);
    
    for(int i=0; i<M; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // (直径, 中心となる頂点)
    vector< pair<int, int> > cand;
    for(int i=0; i<N; i++) {
        if(used[i]) continue;
        pair<int, int> info = get_graph_info(i);
        cand.push_back(info);
    }

    sort(cand.rbegin(), cand.rend());
    vector< pair<int, int> > edges;
    for(int i=1; i<cand.size(); i++) {
        int u = cand[0].second, v = cand[i].second;
        edges.emplace_back(u+1, v+1);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    pair<int, int> whole = get_graph_info(0);
    printf("%lld\n", whole.first);
    for(auto e : edges) {
        printf("%lld %lld\n", e.first, e.second);
    }
    return 0;
}