Blockade -tarjan求割点

链接：https://ac.nowcoder.com/acm/problem/50412
来源：牛客网

题目描述

Byteotia城市有n个城镇，m条双向道路。每条道路连接两个不同的城镇，没有重复的道路，所有城镇连通。
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。

输入描述

输入n,m及m条边。

输出描述

输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。

分析

tarjan判断割点，和蓝书上面的BLO有点类似，区别就是BLO是去边，这里是去点

首先我们可以判断，如果一个点是不是割点，那么即使这个点去除，也不会影响整张图的连通性，所以仅仅是被删除的点和其他点不能进行连接，答案为2 * (n - 1)

如果一个点是割点的话，那么去掉这个点就可以把这张图分成几个树形结构，任意两个树形结构之间不能进行连接，所以我们只需要求树的大小即可

代码

#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;

const int N = 1e5 + 10, M = 1e6 + 10;

int n,m;
int h[N],ne[M],e[M],idx;
int dfn[N],low[N],ti;
int root;
ll ans[N];
ll Size[N];
bool st[N];

void add(int x,int y){
    e[idx] = y,ne[idx] = h[x],h[x] = idx++;
}

void tarjan(int u){
    dfn[u] = low[u] = ++ti;
    int cnt = 0;
    Size[u] = 1;
    ll sum = 0;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!dfn[j]){
            tarjan(j);
            Size[u] += Size[j];
            low[u] = min(low[u],low[j]);
            if(low[j] >= dfn[u]){
                cnt++;
                sum += Size[j];
                if(u != root || cnt > 1) st[u] = true;
                ans[u] += Size[j] * (n - Size[j]);
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
    if(!st[u]) ans[u] = 2 * (n - 1);
    else ans[u] += 1ll * (n - 1) + (n - 1 - sum) * (sum + 1);
}


int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(root = 0;root < n;root++)
        if(!dfn[root])
            tarjan(root);
    for(int i = 1;i <= n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}