2024-12-19

TTPC 2024 Div1. A - Don't Detect Cycle (5D)

AtCoder TTPC 大学コンテスト有志コン NoviSteps5D 二重辺連結成分分解・二重頂点連結成分分解グラフ思わず解きたくなる興味深い良問グラフの橋復元後退解析解空間:O(N!)通りの選択肢マルチテストケース問題 Greedy

面白かった！　解説 AC した！

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の単純無向グラフが与えられる。このグラフの辺の順列であって、次の条件を満たすものを 1 つ求めよ（なければ -1 を出力せよ）。

【条件】
頂点数 $N$ 、辺数 $0$ のグラフに対して、上記の順序にしたがって辺を追加していったとき、「今まさに追加しようとしている辺の端点がすでになんらかのサイクルに属している」という状態が発生しない。

制約

$N, M \le 4000$

考えたこと

最初は、「グラフが辺を共有する複数個のサイクルを持っていたらダメ」なのではないかと考えてしまった。しかし、これには次のような反例があった。これは、辺 (1, 2) を最後に残すことで、実現可能だ。

この辺りから、可能であるための特徴づけがわからなくなって迷走してしまった。ここから解説 AC を目指すことに。次のことが言えるようだ。

グラフに、もし両端点の次数が 2 であるような辺があるならば、その辺を最後に残せば良い
- その辺の端点が、その辺なしでサイクルに含まれることはあり得ないため
- さらに言えば、グラフからそのような辺を除去してしまった問題に帰着可能である
グラフに、もし橋があるならば、それは最初に追加してしまってよい
- 橋はそもそもサイクルに含まれることはないため
- さらに言えば、グラフから橋を除去してしまった問題に帰着可能である

逆に、「橋」も「両端点の次数が 2 である辺」も存在しないグラフは、どの辺 $e = (u, v)$ をとっても、その辺を除外したグラフにおいて、 $u$ または $v$ を含むサイクルが存在することが言える（公式解説参照）。

よって、次の解法が生える。

与えられたグラフに対して、「橋」または「両端点の次数が 2 である辺」が存在する限り、以下のことを繰り返す。

橋は最初に追加することにして、グラフから除去する
両端点の次数が 2 である辺は最後に追加することにして、グラフから除去する

もしグラフの辺をすべて除去できれば、適切な順序付けが構成できる。そうでなければ、適切な順序付けは不可能である。

以上の解法は、 $O(M(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);
    }

    // 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);
        }
    }
};

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N, M, u, v;
        cin >> N >> M;
        Graph<int> G(N);
        for (int i = 0; i < M; i++) {
            cin >> u >> v, u--, v--;
            G.add_edge(u, v, i);
        }

        vector<int> res, former, latter;
        while (true) {
            set<pair<int,int>> ers;

            // erase bridges
            LowLink<int> ll(G);
            for (auto e : ll.brs) {
                former.push_back(e.val);
                ers.insert(minmax(e.from, e.to));
            }

            // erase edges whose endpoints with 2 degree
            vector<int> deg(N, 0);
            for (int v = 0; v < N; v++) {
                for (auto e : G[v]) {
                    if (ers.count(minmax(e.from, e.to))) continue;
                    deg[v]++;
                }
            }
            for (int v = 0; v < N; v++) {
                for (auto e : G[v]) {
                    if (e.from > e.to) continue;
                    if (ers.count(minmax(e.from, e.to))) continue;
                    if (deg[e.from] == 2 && deg[e.to] == 2) {
                        latter.push_back(e.val);
                        ers.insert(minmax(e.from, e.to));
                    }
                }
            }

            if (ers.empty()) break;

            // build new graph
            Graph<int> G2(N);
            for (int v = 0; v < N; v++) {
                for (auto e : G[v]) {
                    if (e.from > e.to) continue;
                    if (ers.count(minmax(e.from, e.to))) continue;
                    G2.add_edge(e.from, e.to, e.val);
                }
            }
            G = G2;
        }

        reverse(latter.begin(), latter.end());
        for (auto v : former) res.push_back(v);
        for (auto v : latter) res.push_back(v);
        if (res.size() < M) {
            cout << -1 << endl;
        } else {
            for (auto id : res) cout << id+1 << " ";
            cout << endl;
        }
    }
}

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

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

TTPC 2024 Div1. A - Don't Detect Cycle (5D)

問題概要

制約

考えたこと

コード