UVa Live Archive 5920 - Kingdom Roadmap

問題

ICPC Regionals 2011 Europe - Northeastern の問題

問題リンク：UVa Live Archive 5920 - Kingdom Roadmap

N頂点の木が与えられる。どの1つの辺を取り除いても全体の連結性が保たれるように辺を追加するとき、必要な辺の最小本数とその追加する場所を求めよ。

• 

解法

どの1つの辺を取り除いても連結であるということは、橋である辺が無いということである。つまり、各辺が1つ以上の閉路に含まれるようにすればよい。

辺のつなぎ方を考える。葉である頂点には少なくとも1本辺を追加する必要があるので葉同士を辺でつないでいくのが最も効率的である。ある2頂点を結ぶと閉路ができ、その2頂点間の最短経路上の辺はすべて閉路に含まれることを利用する。

実装では、葉以外を根とする適当な根付き木をつくり、dfsで親に戻るとき1つ以上葉の頂点を持ちながら戻ればよい(これが辺(u,v)を閉路に含ませることに対応する)。イメージ的には探索で葉の頂点を回収しながら親へ向かう辺をまたがせるような感じである。持っている頂点数が3以上になったら辺でつないで頂点数が2以下になるようにする。葉の頂点数が奇数で最後まで余ったら根とつないでおく。

追加する辺の本数は(葉の頂点数)/2の切り上げとなる。

Code

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

typedef pair<int, int> P;

int n;
vector<vector<int> > g;  // グラフ
vector<P> ans;  // 追加する辺集合

vector<int> rec(int now, int pre){
    vector<int> res;
    if(g[now].size() == 1){  // 葉の頂点である
        res.push_back(now);
    }
    else{
        for(auto& nxt : g[now]){
            if(nxt == pre) continue;
            auto tmp = rec(nxt, now);
            if(res.size() + tmp.size() >= 3){  // 異なる部分木間で葉を結ぶ
                ans.push_back(make_pair(res.back(), tmp.back()));
                res.pop_back();
                tmp.pop_back();
            }
            for(auto& v : tmp) res.push_back(v);
        }
    }
    return res;
}

int main() {
    while(cin >> n){
        ans.clear();
        g.clear();
        g.resize(n);
        // 入力
        for(int i=0;i<n-1;i++){
            int u, v;
            cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        for(int i=0;i<n;i++){
            if(g[i].size()>1){  // 葉でない頂点を根とする
                vector<int> v;
                v = rec(i, -1);  // 根付き木で探索
                if(v.size()==2){  // 余った頂点が2つ
                    ans.push_back(make_pair(v[0], v[1]));
                }
                else{  // 余った頂点が1つ
                    ans.push_back(make_pair(i, v[0]));
                }
                break;
            }
        }
        // 出力
        cout << ans.size() << endl;
        for(auto& e : ans){
            cout << e.first+1 << " " << e.second+1 << endl;
        }
    }
    return 0;
}