Two Fairs [Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) B]

https://codeforces.com/contest/1276/problem/B

解説

https://codeforces.com/contest/1276/submission/66871631

あるx,yについて全ての経路でa,bを通るということは、
頂点a,bを抜くとxからyに到達不可能になるということ。
よって、頂点a,bを抜いた状態で考えてみよう。
頂点a,bを抜いて、unionfindで連結成分をまとめよう。
この連結成分毎に頂点aにつながっているか、bにつながっているか、どちらにもつながっているかを判定する。
求めたい経路はx→a→b→yであるため、頂点aにのみつながっている頂点数×頂点bにのみつながっている頂点数をすると答え。

int N, M, A, B;
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N >> M >> A >> B;
    if (A > B) swap(A, B);
    A--; B--;
    
    UnionFind uf(N);
    vector<int> va, vb;
    vector<int> flag(N);
    int FA = 0x01;
    int FB = 0x02;

    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        if (a > b) swap(a, b);

        if (a == A and b == B) continue;
        else if (a == A) va.push_back(b);
        else if (a == B) vb.push_back(b);
        else if (b == A) va.push_back(a);
        else if (b == B) vb.push_back(a);
        else uf(a, b);
    }
    
    fore(i, va) flag[uf[i]] |= FA;
    fore(i, vb) flag[uf[i]] |= FB;

    ll ta = 0, tb = 0;
    rep(i, 0, N) {
        if (flag[uf[i]] == FA) ta++;
        if (flag[uf[i]] == FB) tb++;
    }

    ll ans = ta * tb;
    printf("%lld\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}