Learning Algorithms

アルゴリズムの勉強メモ

木の直径のパスを一つ挙げるライブラリ

木の直径のパスを一つ挙げるライブラリ

木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題でverify済みです。

中のアルゴリズムは非常に簡単で、次の通りです。

・任意の点を一つ選んで、そこから最も遠い点を一つ固定する(これを $s$ とする)。
・$s$ から最も遠い点を一つ見つける(これを $t$ とする)。
・その2点を両端とするパスを $DFS$ で構築する。
・これが直径のパス(複数ある場合はその一例)になります。

証明は省略です(知らない方はこの問題をご覧ください!)。

//verified by 'http://codeforces.com/contest/911/problem/F'
vector<int> DiameterPath(const vector<vector<int>> &g) {
        int n = g.size();
        if (n == 1) return vector<int> { 0 };
        //startから最も離れた頂点を求める
        auto farthest = [&](int start) {
                vector<int> depth(n);
                function<void (int, int, int)> get_depth = [&](int u, int prev, int d) {
                        depth[u] = d;
                        for (auto v : g[u]) if (v != prev) {
                                get_depth(v, u, d + 1);
                        }
                };
                get_depth(start, -1, 0);
                int maxd = 0;
                int res = 0;
                for (int i = 0; i < n; i ++) {
                        if (depth[i] > maxd) {
                                maxd = depth[i];
                                res = i;
                        }
                }
                return res;
        };
        //両端を決める
        int s = farthest(0);
        int t = farthest(s);
        //パスを構築する
        vector<int> diameter_path;
        function<void (int, int, vector<int> &)> construct = [&](int u, int prev, vector<int> &path) {
                if (u == t) {
                        diameter_path = path;
                        return;
                }
                for (auto v : g[u]) if (v != prev) {
                        path.push_back(v);
                        construct(v, u, path);
                        path.pop_back();
                }
        };
        vector<int> tmp;
        tmp.push_back(s);
        construct(s, -1, tmp);
        return diameter_path;
}

使う時は以下のようにします。

//gは木の隣接リストであるvector<vector<int>>
vector<int> path = DiameterPath(g);
//int s = path.front();
//int t = path.back();

以上です。

もっと簡単に書けるよ!って人がいらっしゃればぜひご教示ください。