問題概要

$1$ 以上 $N$ 以下の整数からなるサイズ $M$ の 2 つの数列 $A_{1}, \dots, A_{M}$ 、 $B_{1}, \dots, B_{M}$ が与えられる。

今、0 と 1 のみからなるサイズ $M$ の文字列 $S$ を自由に作ることができる。この文字列に応じて、次のような頂点数 $2N$ 、辺数 $N+M$ の無向グラフ $G$ を作る。

() 番目の辺は、
- $S_{i}$ が 0 のときは 2 頂点 $(A_{i}, B_{i}+N)$ を結ぶ
- $S_{i}$ が 1 のときは 2 頂点 $(B_{i}, A_{i}+N)$ を結ぶ
( 番目の辺は、
- 2 頂点 $(j, j+N)$ を結ぶ

このグラフの橋の本数が最小となるような文字列 $S$ を 1 つ求めよ。

制約

$1 \le N, M \le 2 \times 10^{5}$

考えたこと

モノグサ社内で、Kano 君たちと一緒に考えた。できるだけグラフ $G$ において、サイクルを形成させたい問題だと言える。たとえば、

$(A, B) = (1, 2), (2, 3), (3, 1)$

のときは、S = "001" が最適となる。これはグラフの辺の向き付けの問題とも言える。つまり、

頂点数 $N$
辺数 $M$ で、2 頂点 $A_{i}, B_{i}$ を結ぶ

としてできる無向グラフ $G'$ において、適切に辺に向きをつける (文字列 $S$ として 0 にするか 1 にするかの選択に対応する) ことで、サイクルを形成させたい問題と言える。

まず、グラフ $G'$ においても橋であるような辺はどのように向き付けしても、グラフ $G$ 上で橋が形成されることは免れない。逆に、グラフ $G'$ において二重辺連結成分分解したときの連結成分については、おそらく

二重辺連結成分の各辺に対して、適切に向き付けをすることで、強連結にすることが可能で、
その方法をとったときに、グラフ $G$ 上で橋が発生しない

というストーリーになるのではないかと考えた。2 はとりあえず正しい。1 はいかにも有名問題っぽいが......

二重辺連結成分は、適切に各辺を向き付けして、強連結にできる

どうもこれは正しいっぽい。具体的には、

1 点を選ぶ
その点を根とした DFS 木を作る
DFS 木上の点は根から遠ざかるように向き付けして、後退辺は逆向きに向き付けする

とすればよい。

そして、今の時点では「二重辺連結成分分解して、各連結成分について DFS 木を作る」という解法が生えているわけだけど、よく考えたら二重辺連結成分分解は不要だ。最初から DFS 木を作れば OK。計算量は $O(N+M)$ となる。

コード

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

using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    vector<int> A(M), B(M);
    for (int i = 0; i < M; ++i) cin >> A[i], --A[i];
    for (int i = 0; i < M; ++i) cin >> B[i], --B[i];
    for (int i = 0; i < M; ++i) {
        G[A[i]].emplace_back(B[i], i+1);
        G[B[i]].emplace_back(A[i], -(i+1));
    }
    
    vector<int> res(M, -1);
    vector<bool> seen(N, false);
    auto dfs = [&](auto self, int v) -> void {
        seen[v] = true;
        for (auto e : G[v]) {
            int id = abs(e.second) - 1;
            if (res[id] == -1) res[id] = (e.second > 0 ? 0 : 1);
            if (seen[e.first]) continue;
            self(self, e.first);
        }
    };
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        dfs(dfs, v);
    }
    
    for (int i = 0; i < M; ++i) cout << res[i];
    cout << endl;
}