https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0366?year=2017
前提知識
考察過程
1. 全体を強連結にせよという問題に言い換えられる
2. 強連結成分については内部で辺を貼る必要は無いので、強連結成分分解をしてDAGにした状態で考えればよさそう
3. 自明そうな所から攻めてみる
4. 「入次数が0の頂点は辺が入ってこないとだめ」「出次数が0の頂点は辺が出てかないとだめ」
5. これが全部満たされれば良さそう?
6. 今回は特に構築せよという問題ではないため、その条件を満たせば、あとは最適に繋げば全体が強連結になりそう
7. 特に何も考えずに投げると通る
解法
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0366/review/3136586/hamayanhamayan/C++14
自分は強連結成分→縮約→トポソの流れをライブラリ化してあるやつがあるので、それを貼る。
(ここではトポソは使わないけど)
縮約してできたDAGについて、「入次数が0の頂点」の数をsource、「出次数が0の頂点」の数をsinkとして数える。
すると必要な辺の数はmax(soruce, sink)となるので、それが答え。
コーナーケースとして、既に全体が強連結な場合は0が答え。
int N, M; SCCtoDAG scctodag; int inedge[101010], outedge[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; scctodag.init(N); rep(i, 0, M) { int s, t; cin >> s >> t; scctodag.add_edge(s, t); } scctodag.build(); if (scctodag.M == 1) { printf("0\n"); return; } int source = 0, sink = 0; rep(cu, 0, scctodag.M) { fore(to, scctodag.newE[cu]) { outedge[cu]++; inedge[to]++; } } rep(cu, 0, scctodag.M) { if (outedge[cu] == 0) sink++; if (inedge[cu] == 0) source++; } int ans = max(source, sink); cout << ans << endl; }