[POI2008] BLO-Blockade

songhn · 2018-05-26 22:55:50 · 题解

首先可以对第i个节点进行讨论

假如i不是割点（即把i和它有关的所有边都去除后图依然联通）那么这个图只有i是独立在外面的，由于求的是有序点对，所以除了i以外的n-1个点作为一个大的连通图对i加边，即为2*(n-1)对

假如i是割点，那么会把图分为a个连通块以及i本身,由于tarjan在求割点的过程中是一棵搜索树往下遍历，所以除了它和它的子树外，还会有其他剩余点共同构成另一个连通块（有点类似树的重心的求法）设i所有子树的和为sum,第i个子树的节点总数为t[i]，点对的数量便为t[1]*(n-t[1])+t[2]*(n-t[2])+\cdots+t[a]*(n-t[a])+(n-1)+(1+sum)*(n-sum-1)

所以在求割点的过程中每遇到一个low[v]>=dfn[u]便把对数加上t[i]*(n-t[i])最后假如不是割点那直接把对数更新为2*(n-1)是割点则加上n-1+(n-sum-1)*(sum+1) 最后遍历输出答案即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,m,head[maxn],num=0;
int dfn[maxn],low[maxn],size[maxn],tot=0;
long long ans[maxn];
bool cut[maxn];
struct node{
    int v,nex;
}e[maxn];
void add(int u,int v)
{
    e[++num].v=v;
    e[num].nex=head[u];
    head[u]=num;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++tot;
    size[u]=1;
    int flag=0,sum=0;
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            size[u]+=size[v];
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                ans[u]+=(long long)size[v]*(n-size[v]);
                sum+=size[v];
                flag++;
                if(u!=1||flag>1) cut[u]=true;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(!cut[u]) ans[u]=2*(n-1);
    else ans[u]+=(long long)(n-sum-1)*(sum+1)+(n-1);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=read(),y=read();
        add(x,y),add(y,x);
    }
    tarjan(1);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}