天下一プログラマーコンテスト2015予選A D - ハシポン
解説(http://tenka1.klab.jp/2015/explain/quala_d.html)微妙に違うような…「葉」の解釈にもよるけど。
解法
概ね解説のとおりなのですが,「葉」と書いてあるところは「次数1の頂点」と読み替えたほうが良いと思います。
typedef long long Weight; // 辺を表す構造体 struct Edge { int src, dst; Weight weight; Edge(int src, int dst) : src(src), dst(dst) {} Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {} }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; void visit(const Graph & g, int v, int u, Edges& brdg, vector< vector<int> >& tecomp, stack<int>& roots, stack<int>& S, vector<bool>& inS, vector<int>& num, int& time) { num[v] = ++time; S.push(v); inS[v] = true; roots.push(v); for (auto e : g[v]) { int w = e.dst; if (num[w] == 0) visit(g, w, v, brdg, tecomp, roots, S, inS, num, time); else if (u != w && inS[w]) while (num[roots.top()] > num[w]) roots.pop(); } if (v == roots.top()) { brdg.push_back(Edge(u, v)); tecomp.push_back(vector<int>()); while (1) { int w = S.top(); S.pop(); inS[w] = false; tecomp.back().push_back(w); if (v == w) break; } roots.pop(); } } // 無向グラフGを与えた時,それを二重辺連結成分分解する // brdgが橋のリスト // tecompが二重辺連結成分のリスト void bridge(const Graph& g, Edges& brdg, vector< vector<int> >& tecomp) { const int n = g.size(); vector<int> num(n); vector<bool> inS(n); stack<int> roots, S; int time = 0; for (int u = 0; u < n; u++) if (num[u] == 0) { visit(g, u, n, brdg, tecomp, roots, S, inS, num, time); brdg.pop_back(); } } vector<vi> G; void dfs(int v, int p, vi& sz, const vector<vi>& tecomp) { sz[v] += tecomp[v].size(); for (int el : G[v]) { if (el == p) continue; dfs(el, v, sz, tecomp); sz[v] += sz[el]; } } void saiki(int v, int p, vi& leaf) { if (G[v].size() == 1) leaf[v]++; for (int el : G[v]) { if (el == p) continue; saiki(el, v, leaf); leaf[v] += leaf[el]; } } int main() { cin.tie(0); ios::sync_with_stdio(false); int V, E; cin >> V >> E; Graph g(V); for (int i = 0; i < E; i++) { int a, b; cin >> a >> b; g[a].emplace_back(a, b); g[b].emplace_back(b, a); } Edges brdg; vector<vi> tecomp; bridge(g, brdg, tecomp); // 木を構成する int n = tecomp.size(); if (n == 1) { cout << "IMPOSSIBLE" << endl; return 0; } G.resize(n); vector<int> trans(V); for (int i = 0; i < n; i++) { for (int el : tecomp[i]) trans[el] = i; } for (Edge e : brdg) { int v = trans[e.src], u = trans[e.dst]; G[u].push_back(v); G[v].push_back(u); } vector<int> sz(n); // 頂点の部分木に実際にある頂点数 vector<int> leaf(n); // 頂点の部分木にある次数1の頂点数(葉ではないような) dfs(0, -1, sz, tecomp); saiki(0, -1, leaf); int ans = INT_MAX; for (Edge e : brdg) { int u = trans[e.src]; int v = trans[e.dst]; if (sz[u] < sz[v]) swap(u, v); // sz[u] > sz[v] if (sz[v] == 2 || V-sz[v] == 2) continue; int sum = 0; if (G[v].size() >= 2) { sum += (leaf[v] + 1 + (G[v].size()==2)) / 2; } if (G[u].size() >= 2) { sum += (leaf[0]-leaf[v]+1+(G[u].size()==2)) / 2; } ans = min(ans, sum); } if (ans == INT_MAX) cout << "IMPOSSIBLE" << endl; else cout << ans << endl; return 0; }