木の直径のパスを一つ挙げるライブラリ
木の直径のパスを一つ挙げるライブラリ
木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題で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();
以上です。
もっと簡単に書けるよ!って人がいらっしゃればぜひご教示ください。