Luogu P3469 [POI2008]BLO-Blockade

[P3469 POI2008]BLO-Blockade - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

图 \(G\) 本身联通。删除 \(u\) 的连边后会形成 \(k \ge 2\) 个连通块（至少会把 \(u\) 隔离出来）。设这些连通块的大小是 \(s_1, \cdots s_k\)，那么答案是 \(s_1 \times (n - s_1) + s_2 \times (n-s_2) + \cdots + s_k \times (n - s_k)\)。

在 \(G\) 上 tarjan。当前节点为 \(u\)，删除 \(u\) 的连边后连通块有三种：

• \(\{u\}\)（一个）；
• 在 \(u\) 在搜索树上的后代 \(v\) 中，满足 \(dfn[v] \ge low[u]\) 的，搜索树上以 \(v\) 为根的子树上的节点集（零个到多个）；
• 上面那两块除去之后剩余所有节点的集合（一个）。

只要在 tarjan 的时候统计就行了。

并不需要统计割点，但是确实运用了这个思想。

\(\mathcal{O}(n+m)\)。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-13 00:45:34 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-13 01:12:38
 */
#include <bits/stdc++.h>
#define int long long

inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

const int maxn = (int)1e5 + 5;

std :: vector <int> G[maxn];

int siz[maxn], low[maxn], dfn[maxn], ans[maxn], times;

int n;

inline bool gmi(int &a, int b) {
    return b < a ? a = b, true : false;
}

inline void tarjan(int u) {
    dfn[u] = low[u] = ++times;
    siz[u] = 1;
    
    ans[u] = n - 1; // 第一种连通块的贡献

    int tot = n - 1; // 第三种连通块的大小，为 n-第一种连通块的大小-第二种的
    // 这里先把第一种的减去（就是1），一会还会减掉第二种的

    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            siz[u] += siz[v];
            gmi(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ans[u] += siz[v] * (n - siz[v]); // 第二种连通块
                tot -= siz[v]; // 第三种连通块大小减去第二种的
            }
        } else
            gmi(low[u], dfn[v]);
    }

    ans[u] += tot * (n - tot); // 第三种连通块
}

signed main() {
    n = read();
    int m = read();
    while (m--) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }

    tarjan(1);

    for (int u = 1; u <= n; ++u)
        printf("%lld\n", ans[u]);
    
    return 0;
}