アリス仕掛けの摩天楼 [yukicoder 977]

https://yukicoder.me/problems/no/977

前提知識

• UnionFind
• 二重辺連結成分分解

解説

https://yukicoder.me/submissions/424691

Aliceは連結成分を最大1つ増やすことができるし、Bobは連結成分を最大1つ減らすことができる。
Bobが連結成分をへらすことができない条件は連結成分が1つであることだけなので、基本的にはできる。
Aliceが勝つためには、Bobの手番の時に連結成分が3つ以上ある場面を作ることが要求される。
それ以外ならBobがくっつけて勝てる。

Aliceが適切な操作を行って、連結成分を3つ以上にできるかを判定しよう。
ある辺を削除した時に、連結成分が増える辺のことを「橋」という。
よって、橋が存在するなら連結成分を+1することができるし、なければできない。
解法としては「UnionFindで連結成分の数を計算→二重辺連結成分分解を行い橋を検出」を行う。
橋の検出に二重辺連結成分分解がやりすぎかもしれないが、ライブラリ貼るだけなので採用した。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    UnionFind uf(N);
    BridgeSCC scc; scc.init(N);

    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        uf(a, b);
        scc.add_edge(a, b);
    }

    scc.scc();

    int cnt = 0;
    rep(i, 0, N) if (uf[i] == i) cnt++;
    if (0 < scc.BR.size()) cnt++;

    if (3 <= cnt) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}