问题描述:

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

输入:

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

输出:

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

思路:

这道题与无向图的联通性有关,所以可以利用点双联通分量的相关知识。

首先考虑如果点i不为割点,那么答案就是$(n-1)*2$。如果它为割点,那么就把这张图分为了若干块,然后利用乘法原理我们就可以根据每个联通块的大小计算出答案。

然后就考虑如何计算删去某个点后的各个联通块大小。在执行tarjan过程中会产生一棵搜索树,于是我们可以利用这点,用类似于树形DP的方法求出它的各个子树大小。如果这个点是割点,那么每一个子树和剩下部分都是相互独立的,所以我们可以这样计算出各个联通块大小。

代码:

#include <bits/stdc++.h>
#define LL long long
#define MAXE 500005
#define MAXN 100005
using namespace std;

int n, m, cnt, id, head[MAXN], low[MAXN], dfn[MAXN], size[MAXN];
LL ans[MAXN];

struct Edge {int next, to;} edge[MAXE*2];

void addedge(int x, int y)
{
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    head[x]=cnt;
}

void tarjan(int x)
{
    int tag=0, sum=0; bool flag=false;
    low[x]=dfn[x]=++id; size[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(dfn[to]) low[x]=min(low[x], dfn[to]);
        else
        {
            tarjan(to);
            size[x]+=size[to];
            low[x]=min(low[x], low[to]);
            if(low[to]>=dfn[x])
            {
                tag++;
                if(x!=1 || tag>1) flag=true;
                ans[x]+=(LL)size[to]*(n-size[to]);
                sum+=size[to];
            }
        }
    }
    if(flag) ans[x]+=(LL)(n-sum-1)*(sum+1)+n-1;
    else ans[x]=(n-1)*2;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    tarjan(1);
    for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注