2025-01-03

天下一プログラマーコンテスト2015予選A D - ハシポン (3D, 試験管橙色)

AtCoder unrated公式コン橙色diff NoviSteps3D 二重辺連結成分分解・二重頂点連結成分分解場合分けコーナーケースパリティ最小回数・最小個数を求める最適化問題

とても面白かった。場合分けを詰め切るが大変だった。

問題へのリンク

問題概要

橋がただ 1 つだけ存在するような連結で単純な無向グラフをハシポンとよぶ。

頂点数 $N$ 、辺数 $M$ の連結で単純な無向グラフが与えられる。このグラフに辺を追加することで、ハシポンになるようにしたい。これを達成するために追加する辺の本数の最小値を求めよ。不可能である場合は "IMPOSSIBLE" と出力せよ。

制約

$N \le 10^{5}$
$M \le 1.5 \times 10^{5}$

考えたこと

まずは二重辺連結成分分解をして、Bridge-Block 木（ $T$ とする）を作ろう。そして、次のように場合分けして考えた。

木 $T$ のサイズが 1 のとき："IMPOSSIBLE"
木 $T$ のサイズが 2 のとき：すでにハシポンなので 0 本
木のサイズが 3 のとき：
- もし木 $T$ のどの頂点も、ただ 1 個の頂点からなるとき："IMPOSSIBLE"（単純性を破壊してしまうため）
- そうでないとき：辺を 1 本追加してハシポンにできるので、1 本
木 $T$ のサイズが 4 以上のとき：（後述）

木 $T$ のサイズが 4 以上のとき

大前提として、木 $T$ に葉が 3 個以上あればかならずハシポンにできる。そして、木 $T$ のサイズが 4 以上のときは、葉が 2 個しかないとしても、木 $T$ は「長さ 3 以上のパスグラフ」であり、単純性を破壊せずに辺を 1 本追加してハシポンにできる。以上から、木 $T$ のサイズが 4 以上のときはかならずハシポンにすることが可能である。

最小本数の辺を挿入してハシポンにするためには、基本的には「葉」同士を結んでいけば良いだろう。ただし、もし葉が奇数個あって、「1 個だけ残った葉」が 2 本以上の橋をつないだ先端にあるような状態だと、ハシポンにはならないことに注意しよう。そこで、次の値を求めることにする。

leaf_ num：木 $T$ の葉の個数
exist_length_one_bridge：ある葉が存在して、その葉に接続する辺を削除しても葉が増えないとき True / そうでないとき False

このとき、次のように整理できる。

exist_length_one_bridge = True のとき：答えは leaf_num / 2 個
exist_length_one_bridge = False のとき：答えは (leaf_num + 1) / 2 個

後者については補足する。もし leaf_num が奇数であれば、葉を 1 個だけ残して他を潰したとしても、2 本以上の橋が残ってしまう。そのため、さらに追加で 1 本必要である。

以上の解法は $O(N + M)$ の計算量である。

コード

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

// Edge Class
template<class T> struct Edge {
    int from, to;
    T val;
    Edge() : from(-1), to(-1), val(-1) { }
    Edge(int f, int t, T v = -1) : from(f), to(t), val(v) {}
    friend ostream& operator << (ostream& s, const Edge& e) {
        return s << e.from << "->" << e.to;
    }
};

// graph class
template<class T> struct Graph {
    vector<vector<Edge<T>>> list;
    
    Graph() { }
    Graph(int n) : list(n) { }
    Graph(const Graph<T> &G) : list(G.list) { }
    void init(int n) {
        list.assign(n, vector<Edge<T>>());
    }
    Graph &operator = (const Graph &g) {
        list = g.list;
        return *this;
    }

    const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
    const size_t size() const { return list.size(); }
    const void clear() {
        list.clear();
    }
    const void resize(int n) {
        list.resize(n);
    }

    void add_edge(int from, int to, T val = -1) {
        list[from].push_back(Edge(from, to, val));
        list[to].push_back(Edge(to, from, val));
    }

    friend ostream &operator << (ostream &s, const Graph &G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << " -> ";
            for (const auto &e : G[i]) s << e.to << " ";
            s << endl;
        }
        return s;
    }
};

// low-link
template<class T> struct LowLink {
    // results
    vector<int> ord, low;
    vector<int> aps;         // articulation points
    vector<Edge<T>> brs;     // brideges

    // constructor
    LowLink() { }
    LowLink(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // solver
    int dfs(const Graph<T> &G, int t, int v, int p) {
        ord[v] = low[v] = t++;
        int num_of_children = 0;
        bool exist_articulation = false, is_multiple_edge = false;
        for (const auto &e : G[v]) {
            if (ord[e.to] == -1) {
                num_of_children++;
                t = dfs(G, t, e.to, v);
                low[v] = min(low[v], low[e.to]);  // forward edge of DFS-tree
                exist_articulation |= (p != -1) && (low[e.to] >= ord[v]);
                if (ord[v] < low[e.to]) brs.push_back(e);
            } else if (e.to != p || is_multiple_edge) {
                low[v] = min(low[v], ord[e.to]);  // back edge
            } else {
                is_multiple_edge = true;
            }
        }
        if (exist_articulation || (p == -1 && num_of_children > 1)) {
            aps.emplace_back(v);
        }
        return t;
    }

    void solve(const Graph<T> &G) {
        ord.assign(G.size(), -1), low.assign(G.size(), -1);
        for (int v = 0, k = 0; v < (int)G.size(); v++) {
            if (ord[v] == -1) k = dfs(G, k, v, -1);
        }
    }
};

// Two-Edge-Connected Components decomposition
template<class T> struct TwoEdgeConnectedComponentsDecomposition {
    // results
    LowLink<T> ll;
    vector<int> cmp;
    vector<vector<int>> groups, tree;

    // constructor
    TwoEdgeConnectedComponentsDecomposition() { }
    TwoEdgeConnectedComponentsDecomposition(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // getter, bridge-block tree to orignal graph（v: node-id of bridge-block tree)
    int get_size(int v) const {
        return groups[v].size();
    }
    vector<int> get_group(int v) const {
        return groups[v];
    }

    // solver
    int dfs(const Graph<T> &G, int t, int v, int p) {
        if (p >= 0 && ll.ord[p] >= ll.low[v]) cmp[v] = cmp[p];
        else cmp[v] = t++;
        for (const auto &e : G[v]) {
            if (cmp[e.to] == -1) t = dfs(G, t, e.to, v);
        }
        return t;
    }

    void solve(const Graph<T> &G) {
        ll.init(G);
        cmp.assign(G.size(), -1);
        int t = 0;
        for (int v = 0; v < (int)G.size(); v++) {
            if (cmp[v] == -1) t = dfs(G, t, v, -1);
        }
        groups.resize(t);
        tree.resize(t);
        for (int v = 0; v < (int)G.size(); v++) {
            groups[cmp[v]].push_back(v);
        }
        for (const auto &e : ll.brs) {
            int u = cmp[e.from], v = cmp[e.to];
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
    }
};


// 天下一プログラマーコンテスト2015予選A D - ハシポン
void Tenka_2015_A_D() {
    int N, M, a, b;
    cin >> N >> M;
    Graph<int> G(N);
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        G.add_edge(a, b);
    }
    TwoEdgeConnectedComponentsDecomposition<int> tecc(G);
    auto tree = tecc.tree;

    if (tree.size() == 1) {
        cout << "IMPOSSIBLE" << endl;
        return;
    } else if (tree.size() == 2) {
        cout << 0 << endl;
        return;
    } else if (tree.size() == 3) {
        bool allone = true;
        for (auto g : tecc.groups) if (g.size() > 1) allone = false;
        if (allone) cout << "IMPOSSIBLE" << endl;
        else cout << 1 << endl;
        return;
    }

    int leaf_num = 0;
    bool exist_length_one_bridge = false;
    for (int v = 0; v < tree.size(); v++) {
        if (tree[v].size() == 1) {
            leaf_num++;
            int v2 = tree[v][0];
            if (tree[v2].size() > 2) exist_length_one_bridge = true;
        }
    }
    if (exist_length_one_bridge) {
        cout << leaf_num / 2 << endl;
    } else {
        cout << (leaf_num + 1) / 2 << endl;
    }
}


int main() {
    Tenka_2015_A_D();
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

天下一プログラマーコンテスト2015予選A D - ハシポン (3D, 試験管橙色)

問題概要

制約

考えたこと

木 $T$ のサイズが 4 以上のとき

コード

問題概要

制約

考えたこと

木 のサイズが 4 以上のとき

コード

木 $T$ のサイズが 4 以上のとき