Given a connected undirected graph with $n$ nodes and $m$ edges, and two distinct nodes $a$ and $b$, count unordered pairs $(u, v)$ where $u < v$ such that:

• $u \neq a$, $u \neq b$, $v \neq a$, $v \neq b$
• Every path from $u$ to $v$ passes through both $a$ and $b$

Approach

The solution involves identifying nodes separated from $b$ when $a$ is removed, and nodes separated from $a$ when $b$ is removed:

1. From $b$, perform BFS blockign $a$. Nodes unreachable form set $T$ (excluding $a$, $b$).
2. From $a$, perform BFS blocking $b$. Nodes unreachable form set $V$ (excluding $a$, $b$).
3. Valid pair are combinations of nodes from $T$ and $V$, totaling $|T| \times |V|$.

Solution Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, hub1, hub2;
    cin >> n >> m >> hub1 >> hub2;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> visited1(n + 1, false);
    queue<int> q;
    q.push(hub2);
    visited1[hub2] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int neighbor : adj[cur]) {
            if (neighbor == hub1) continue;
            if (!visited1[neighbor]) {
                visited1[neighbor] = true;
                q.push(neighbor);
            }
        }
    }

    int group1_count = 0;
    for (int i = 1; i <= n; i++) {
        if (i == hub1 || i == hub2) continue;
        if (!visited1[i]) group1_count++;
    }

    vector<bool> visited2(n + 1, false);
    queue<int> q2;
    q2.push(hub1);
    visited2[hub1] = true;
    while (!q2.empty()) {
        int cur = q2.front();
        q2.pop();
        for (int neighbor : adj[cur]) {
            if (neighbor == hub2) continue;
            if (!visited2[neighbor]) {
                visited2[neighbor] = true;
                q2.push(neighbor);
            }
        }
    }

    int group2_count = 0;
    for (int i = 1; i <= n; i++) {
        if (i == hub1 || i == hub2) continue;
        if (!visited2[i]) group2_count++;
    }

    long long result = static_cast<long long>(group1_count) * group2_count;
    cout << result << endl;

    return 0;
}