mayoko’s diary

プロコンとかいろいろ。

天下一プログラマーコンテスト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;
}