洛谷3469 [POI2008]BLO-Blockade

题意

给出一个无向图，对于每个节点 $i$ ，求如果去掉这个节点有多少对点不能连通。

其中点数 $N\le 100000$ ，边数 $M\le 500000$ 。

题解

因为是求点对，所以所有答案都要 $\times 2$ 。

先考虑去掉的这个点，其它点都不能和它连通，所以 $ans+=(n-1)\times 2$ 。

如果这个点是割点，那么去掉这个点还会对图上其它点有影响。

在 $Tarjan$ 过程中记录以当前节点为根子树大小 $siz[]$ ，以及已经计算过的点的个数 $left$ 。如果当前点是割点，那么 以它的每一个子节点为根的子树 都无法与图的其它部分连通，所以 $ans+=siz[y]\times (N-left)\times 2$ 。

当然要先把当前节点算进已经计算过的节点来去重 $left+=siz[y]$ 。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to;
} edge[1000005];
ll cnt,head[100005],n,m,a,b,ans[100005];
ll id[100005],low[100005],siz[100005],dfsord;

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(ll x,ll f)
{
    id[x]=low[x]=++dfsord;
    siz[x]=1;
    ans[x]=n*2-2;
    ll left=1;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==f) continue;
        if (!id[y])
        {
            dfs(y,x);
            low[x]=min(low[x],low[y]);
            siz[x]+=siz[y];
            if (id[x]<=low[y])
            {
                left+=siz[y];
                ans[x]+=siz[y]*(n-left)*2;
            }
        }
        else low[x]=min(low[x],id[y]);
    }
}

int main()
{
    n=read(); m=read();
    for (ll i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    for (ll i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i,0);
    }
    for (ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}