https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/C
前提知識
考察過程
1. なもりグラフというのがあり、1つだけ閉路がある
2. aもbも閉路上にあれば2本の削除が必要
3. それ以外なら1本で十分
解法
https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149707
なもりグラフはだた一つの閉路を持つので、閉路を構成する頂点をまずは見つける。
dfsを使おう。
任意の頂点から始めて、vis変数で既に訪れたかを確認しながら進めていく。
もし、vis変数で既に訪れている遷移先を見つけた場合は、閉路が見つかったことになるので、
そこから、1つずつ戻って閉路に含まれる頂点に印をつけていく。
戻っていったときに、自分が既に閉路に含まれる頂点になっていたら、始点まで戻ってきたことになる。
あとは、クエリのどちらも閉路に含まれるなら、2。
そうでないなら、1が答え。
int N, Q; vector<int> E[101010]; //--------------------------------------------------------------------------------------------------- int heiro[101010], vis[101010]; int dfs(int cu, int pa = -1) { vis[cu] = 1; fore(to, E[cu]) if (to != pa) { if (vis[to] == 1) { heiro[to] = 1; heiro[cu] = 1; return 1; } else { if (dfs(to, cu)) { if (heiro[cu] == 1) return 0; heiro[cu] = 1; return 1; } } } return 0; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) { int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } dfs(0); cin >> Q; rep(_, 0, Q) { int a, b; cin >> a >> b; a--; b--; if (heiro[a] and heiro[b]) printf("2\n"); else printf("1\n"); } }