TIOJ 2050 尋找關節點 EXTREME 題解

TIOJ 2050

題敘

有一個無向圖 $(n \le 2000, m \le \frac{n \cdot (n-1)}{2})$ ，求有幾個點對 $(u, v)$，將其移除之後此圖不連通。

解法

核心概念是：枚舉 $u$，然後將剩下的圖跑 Tarjan’s Find AP Algorithm，找到的 AP 就會是 $v$。除此之外，原圖中任兩個 AP 刪除也會是合法的點對。

但是這樣會有一個問題，就是它有可能是一個完全圖，這會導致我們跑一次 Tarjan’s 時的複雜度來到 $\mathcal{O}(n^2)$，而我們跑 $n$ 次 Tarjan’s 的複雜度就會來到 $\mathcal{O}(n^3)$。

這時候就得拿出一個超酷的縮邊技巧了（據說是選訓教授教的），我們可以對原圖做三次 BFS，其中三次 BFS 所用的邊皆不重複，然後接下來的 Tarjan’s 通通都用這三個 BFS 生成樹所使用的邊去找，就可以將單次 Tarjan’s 的複雜度壓到 $\mathcal{O}(n)$ 了。至於這樣做為什麼會對我也還看不懂，不過 Wiwihorz 有將證明過程放在這裡，有興趣的可以去看看。

Code

#define MAXN 2005
#define MAXM 1000005 
int n, m;
vector<int> G[MAXN];
vector<pii> g[MAXN];
vector<pii> E;
bitset<MAXN * MAXN> used;
bool ans[MAXN][MAXN];

struct Tarjan_AP {
    int low[MAXN], dep[MAXN], timestamp = 0;
    bitset<MAXN> isAP;
    vector<int> AP;

    void dfs(int i, int fa, int rm) {
        dep[i] = low[i] = ++timestamp;
        int chdcnt = 0;

        for (int e: G[i]) {
            if (e == rm)
                continue;

            if (!dep[e] || dep[e] > timestamp) {
                dfs(e, i, rm);
                chdcnt++;
                cmin(low[i], low[e]);
                if (low[e] >= dep[i])
                    isAP[i] = true;
            }
            cmin(low[i], dep[e]);
        }

        if (i == fa && chdcnt < 2)
            isAP[i] = false;
        if (isAP[i])
            AP.pb(i);
    }

    void main(int rm) {
        timestamp = 0;
        MEM(dep, 0);
        isAP.reset();
        AP.clear();

        dfs(rm % n + 1, rm % n + 1, rm);
    }
} AP;


void sol() {
    cin >> n >> m;
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        g[a].pb({b, i});
        g[b].pb({a, i});
        E.pb({a, b});
    }


    for (int i = 0; i < 3; i++) {
        bitset<MAXN> vis;
        for (int j = 1; j <= n; j++) {
            if (vis[j])
                continue;
            queue<int> q;
            q.push(j);
            vis[j] = true;

            while(q.size()) {
                auto now = q.front();
                q.pop();
                for (auto e: g[now]) {
                    if (used[e.S] || vis[e.F])
                        continue;
                    q.push(e.F);
                    vis[e.F] = true;
                    used[e.S] = true;
                }
            }
        }
    }

    for (int i = 0; i < m; i++) {
        if (!used[i])
            continue;
        G[E[i].F].pb(E[i].S);
        G[E[i].S].pb(E[i].F);
    }

    int cnt = 0;

    AP.main(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (AP.isAP[j] && AP.isAP[i]) {
                cnt += !ans[j][i];
                ans[j][i] = true;
            }
        }
    }


    for (int i = 1; i <= n; i++) {
        AP.main(i);
        for (int it: AP.AP) {
            cnt += !ans[min(it, i)][max(it, i)];
            ans[min(it, i)][max(it, i)] = true;
        }
    }

    cout << cnt << endl;
}