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