はまやんはまやんはまやん

hamayanhamayan's blog

な◯りカット (Namo.. Cut) [Aizu Competitive Programming Camp 2018 Day 3 C]

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