[POI2008]BLO

Description

Byteotia城市有\(n\)个 towns \(m\)条双向roads. 每条 road 连接两个不同的 towns ,没有重复的road. 所有towns连通。

Input

输入\(n<=100000\) \(m<=500000\)及\(m\)条边

Output

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

Sample Input

5 5

1 2

2 3

1 3

3 4

4 5

Sample Output

8

8

16

14

8

考虑到求图中的割点。

图中有两种点

\(1.\)该点不为割点，由割点定义，切掉该点后，剩下的\(n-1\)个点仍然联通，所以答案为\(2*(n-1)\)。

\(2.\)该点为割点，所以，在切掉该点后，图中会出现若干个联通块，我们需要求出每个联通块的大小，两两相乘再相加。

我们不妨在\(tarjan\)的过程中，搜索出每棵“子树”的\(size\)。

综上所述，在删除掉一个割点\(i\)后，不联通的有序对数量为：

\(size[S1]*(n-size[S1])+size[S2]*(n-size[S2])+...+size[St]*(n-size[St])+2*(n-1)+(n-size[i])*(size[i]-1)\)

#include<bits/stdc++.h>

#define lll long long

using namespace std;

int read()

{

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*w;

}

const int N=100010;

int n,m,cnt,visnum,x,y;

int head[N],dfn[N],low[N],cut[N],size[N];

lll ans[N];

struct node{

    int to,next;

}edge[10*N];

void add(int x,int y)

{

    cnt++;edge[cnt].to=y;edge[cnt].next=head[x];head[x]=cnt;

}

void tarjan(int k,int fa)

{

    dfn[k]=low[k]=++visnum;int flag=0;lll num=0;

    for(int i=head[k];i;i=edge[i].next)

    {

        int v=edge[i].to;if(v==fa) continue;

        if(!dfn[v])

        {

            tarjan(v,k);low[k]=min(low[k],low[v]);size[k]+=size[v];

            if(dfn[k]<=low[v])

            {

                flag++;

                if(fa!=0||flag>1)

                {

                    cut[k]=1;ans[k]+=(lll)size[v]*num;

                    num+=size[v];

                }

            }

        }

        else low[k]=min(low[k],dfn[v]);

    }

    ans[k]+=(lll)((n-num-1)*num);

    size[k]++;

}

int main()

{

    n=read();m=read();

    for(int i=1;i<=m;i++)

    {

        x=read();y=read();

        add(x,y);add(y,x);

    }

    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);

    for(int i=1;i<=n;i++) printf("%lld\n",2*(ans[i]+n-1));

}

巴特西

[POI2008]BLO（Tarjan）