Blockade

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1910 字
给n个点m条边的连通无向图，对每个点i输出删
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1526
// 题意：给 n 个点 m 条边的连通无向图，对每个点 i 输出删掉 i 之后有多少个有序点对 (x, y) 变得无法互通（x、y 不等于 i 时按是否同块统计，含 i 的点对也算不互通）。
// 思路：从 1 号点跑 Tarjan，记下每棵子树的规模 sub。对点 u，凡满足 low[v] >= dfn[u] 的儿子子树各成一块，其余部分（祖先加未被切开的儿子子树）合成一块，答案就是 2 * (n - 1) 加上「所有块两两之间有序点对数」。
// 1. 含 u 的有序点对恒为 2 * (n - 1) 个，所以先把这一项加上，剩下的只算其余 n - 1 个点跨块的有序对。
// 2. 设各块大小为 g，跨块有序点对数为 (n - 1) 的平方减去各 g 的平方和，不用两两枚举。
// 复杂度：O(n + m) 时间 / O(n + m) 空间
// 易错点：答案量级是 n 的平方，必须用 long long，用 int 会在 n 到 1e5 时直接溢出。
// 易错点：DFS 树的根没有祖先方向，它的「其余部分」大小为 0，公式对每个点统一处理即可，不必给根单独开特例。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 1000005;
int head[MAXN], to[MAXM], nxt[MAXM], ecnt = 1;
int dfn[MAXN], low[MAXN], idx;
int sub[MAXN];
long long ans[MAXN];
int n, m;
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u, int ine){
    dfn[u] = low[u] = ++idx;
    sub[u] = 1;
    long long allchild = 0;
    long long merged = 0;
    long long sqsum = 0;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v, i);
            sub[u] += sub[v];
            low[u] = min(low[u], low[v]);
            allchild += sub[v];
            if(low[v] >= dfn[u]) sqsum += (long long)sub[v] * sub[v];
            else merged += sub[v];
        }
        else if(i != (ine ^ 1)){
            low[u] = min(low[u], dfn[v]);
        }
    }
    long long rest = (long long)(n - 1) - allchild + merged;
    long long tot = (long long)(n - 1) * (n - 1) - sqsum - rest * rest;
    ans[u] = 2LL * (n - 1) + tot;
}
int main(){
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i, 0);
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}
Blockade

正文

一本通·提高篇的其它内容
