【BZOJ1123】[POI2008]BLO

2015.08.03 14:42 Mon | 32次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

输入n<=100000 m<=500000及m条边

Output

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

题解

嗯双连通分量都有点不会了……
把割点求出来,同时在dfs的过程中记录搜索树上每个子树的大小。
如果一个点是割点,就把被它分割开的子节点的子树大小乘起来。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define N 100005
int n,m;
#define ll long long
ll ans[N];
struct edge{
    int to,next;
}e[N*10];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int tim,dfn[N],low[N],siz[N],siz2[N];
vector<int> son[N];
void dfs(int u)
{
    low[u]=dfn[u]=++tim;siz[u]=1;siz2[u]=1;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    {
        v=e[i].to;
        if(!dfn[v])
        {
            dfs(v);siz[u]+=siz[v];
            if(low[v]>=dfn[u]) 
            {
                siz2[u]+=siz[v];
                for(int j=0;j<son[u].size();j++)
                ans[u]+=siz[v]*son[u][j];
                son[u].push_back(siz[v]);
            }
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
    }
    for(int j=0;j<son[u].size();j++)
    ans[u]+=(n-siz2[u])*son[u][j];
    ans[u]*=2;
}
int main()
{
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);    
    }
    dfs(1);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]+2*(n-1));
}```