洛谷3469 [POI2008]BLO-Blockade

access_time    bookmark 题解    comment 0 条评论    省选/NOI-

题意

给出一个无向图,对于每个节点 $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;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。