AOJ 2891 な◯りカット (AUPC 2018 day3 C)

サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことを、なもりグラフと呼ぶことにする。

問題へのリンク

問題概要

N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。

• 2 頂点 a, b の間を分断するのに最小何個の辺を除去すればよいか

考えたこと

• a と b がともになもりサイクル上にあるとき 2
• a または b の少なくとも一方が、なもりの "足" 上にあるとき、足を切ればいいので 1

なもりの検出は、BFS によって、「次数 1 の頂点」を Greedy にドンドン削ることで、足をそぎ落とすのが楽。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
vector<vector<int> > G;
vector<int> deg;
vector<int> isin_namori;

int main() {
    cin >> N;
    G.clear(); G.resize(N);
    deg.assign(N, 0);
    for (int i = 0; i < N; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++deg[u], ++deg[v];
    }
    queue<int> que;
    isin_namori.assign(N, 1);
    for (int v = 0; v < N; ++v)
        if (G[v].size() == 1)
            que.push(v), isin_namori[v] = 0;
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (!isin_namori[nv]) continue;
            --deg[nv];
            if (deg[nv] <= 1) {
                isin_namori[nv] = 0;
                que.push(nv);
            }
        }
    }
    int Q; cin >> Q;
    for (int _ = 0; _ < Q; ++_) {
        int a, b; cin >> a >> b; --a, --b;
        if (isin_namori[a] && isin_namori[b]) cout << 2 << endl;
        else cout << 1 << endl;
    }
}