AUPC 2018 day3 C: Namo.. Cut
問題
無向木に一本だけ無向辺を足したグラフが与えられる。
次のQ個のクエリに答えよ。
aからbへのパスをなくすために最小で何本の辺を消せばいいか。
制約
グラフのサイズとクエリの数が両方10万以下。
方針
グラフの作り方から、与えられたグラフにはサイクルがただ一つ存在する。
明らかにa, bがともにサイクル上に存在したら答えは2, そうでないなら1.
サイクル検出は頂点をスタックに積みながらDFSして、同じ頂点に二度目にきたらスタック上の頂点を見るなどする。
サイクル以外の頂点(次数が1)を削除できるだけしていってもよい。DFSのほうが実装楽だと思う。
ソースコード
int n; vector<vector<int>> e; vector<int> stk; set<int> lp, vis; bool rec(int c, int p){ vis.insert(c); stk.push_back(c); for(int i : e[c]) if(i != p){ if(vis.count(i)){ for(int j = stk.size() - 1; ; j--){ lp.insert(stk[j]); if(stk[j] == i) break; } return 1; }else if(rec(i, c)) return 1; } stk.pop_back(); return 0; } int main() { cin.tie(0); cin.sync_with_stdio(0); cin >> n; e.resize(n); rep(i, n){ int a, b; cin >> a >> b; a--; b--; e[a].push_back(b); e[b].push_back(a); } rec(0, 0); int q; cin >> q; while(q--){ int a, b; cin >> a >> b; a--; b--; cout << (lp.count(a) && lp.count(b) ? 2 : 1) << endl; } return 0; }