P3469 [POI2008]BLO-Blockade

P3469 [POI2008]BLO-Blockade

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
const int M=2e6+5;

int h[N],ne[M],e[M],tot;
void add(int from,int to) {
    e[++tot]=to;
    ne[tot]=h[from];
    h[from]=tot;
}

int n,m;
ll ans[N];
int dfn[N],low[N],cnt;
int tmp[N],siz[N];

void tarjan(int now,int rot) {
    dfn[now]=low[now]=++cnt;
    int son=0;
    siz[now]=1;
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(dfn[to]==0) {
            tarjan(to,rot);
            siz[now]+=siz[to];
            low[now]=min(low[now],low[to]);
            if(low[to]>=dfn[now])
                if(++cnt>1||now!=rot) {
                    ans[now]+=1ll*siz[to]*(n-siz[to]-1);
                    tmp[now]+=siz[to];
                }
        }
        else low[now]=min(low[now],dfn[to]);
    }
    ans[now]+=1ll*tmp[now]*(n-tmp[now]-1);
}
//贡献值就是不同的连通块之间两两组合的结果

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)tarjan(i,i);
    for(int i=1;i<=n;i++)
        cout<<ans[i]+(n-1)*2<<endl;
    return 0;
}