第一题 B城

原题连接

题目描述

B城有 $n$ 个城镇，$m$ 条双向道路。

每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。

把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来$m$行，每行包含两个整数 $a$ 和 $b$，表示城镇 $a$ 和 $b$ 之间存在一条道路。

输出格式

输出共$n$行，每行输出一个整数。

第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点$（x，y）$，满足$ x$ 和$ y$ 不连通。

数据范围

$$ n \le 100000 \\\\ m \le 500000 $$

输入样例：

5 5
1 2
2 3
1 3
3 4
4 5

输出样例：

8
8
16
14
8

解题报告

题意理解

一张图,每次删除一个节点,包括它和其他节点的边,问删除这个节点过后,会有多少个有序节点$(x,y)$之间无法连通.

Hint:有序节点$(x,y)$和有序节点$(y,x)$不是同样的节点对.我们要计算两次.

算法解析

删除一个节点,使得图不连通,这不就是割点的定义吗?

1. 假如删掉的节点不是割点.

此时我们发现,除了这个节点与其他节点都不连通,其他节点都是连通的.

因此答案为.
$$ ans=2 \times (n-1) $$
也就是除了当前节点,其余的$(n-1)$个节点都与当前节点不连通.(自己和自己当然是连通的)

然后答案要计算两遍,因此$(n-1) \times 2$

1. 假如说删除的节点是割点

删除割点,会使得图变得四分五裂,成为了若干个连通块.

那么连通块本身内部的节点,当然还是互相连通的.

但是两个不同的连通块的节点,显然就不连通了.

比如说$a$节点属于$1$号连通块.

然后$b$节点属于$2$号连通块.

请问他们连通吗?

不连通!

所以答案+1.

那么我们从特解到通解.

假如说此时有$1,2,3,4,5$这五个连通块.

我们提出一个概念.
$$ size[i]表示i连通块的节点数 $$
而且$s$节点属于$1$号连通块.

那么除了自己所在$1$号连通块内部节点与自己连通,其他连通块节点和自己都没有任何关系.

因此我们得出如下公式.

显然与$s$节点相连的节点个数有
$$ size[x]-1 $$
那么与$s$节点不连通的节点个数有
$$ n-(size[x]-1)-1=n-size[x] \\\\ 总节点-与s节点相通的节点总数-s自身节点=与s不连通的节点数 $$
那么$s$节点的贡献是什么呢?
$$ s号节点的贡献=(n-size[1]) $$
因此我们推出一个连通块贡献的价值.
$$ size[s_1] \times (n-size[s_1]) $$
但是一个割点显然不会只有1个连通块,我们假设它有
$$ s_1,s_2,s_3,s_4,......,s_k连通块. $$
因此一个割点的子连通块贡献了.
$$ size[s_1] \times (n-size[s_1])+size[s_2] \times(n-size[s_2])+…+size[s_k] \times (n-size[s_k]) $$
所有儿子连通块+自身,一共有多少个节点呢,我们算一下.
$$ 1+\sum_{i=1}^ksize[s_i] $$
但是根据搜索树定义,割点有自己的儿子连通块,当然也就有不是儿子连通块.

因此我们得出不是儿子连通块的个数为.
$$ (n-(1+\sum_{i=1}^ksize[s_i])) $$
其实也就是.
$$ n-(1+(size[s_1]+size[s_2]+…+size[s_k])) \\\\ -1,是因为还要抛去自身这个节点 \\\\ Hint:一棵树等于子树节点+根节点. $$
那么这些不是儿子连通块,显然与是儿子联通块是不连通了,因为删除这个割点,所以贡献代价为
$$ (n-(1+\sum_{i=1}^ksize[s_i])) \times (1+\sum_{i=1}^ksize[s_i]) $$
此时我们还要知道,节点自身也是有贡献的,毕竟和其他节点都不连通.
$$ (n-1) \times 1 $$
那么总和上面贡献,就是最终答案了.我就不打了,上面很清晰了,下面也有代码解释.

代码解析

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+200;
long long head[N],edge[N],Next[N],tot,num,ans[N],root;
long long n,m,size[N],dfn[N],low[N];
bool cut[N];
void add_edge(int a,int b)//加边
{
    edge[++tot]=b;
    Next[tot]=head[a];
    head[a]=tot;
}
void Tarjan(int x)
{
    dfn[x]=low[x]=++num;//编号
    size[x]=1;//初始时候就自己这一个孤寡老人
    int flag=0,sum=0;
    for (int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];//儿子节点
        if (!dfn[y])//不曾访问
        {
            Tarjan(y);//访问
            size[x]+=size[y];//儿子节点贡献的子树大小
            low[x]=min(low[x],low[y]);//更新一下
            if (low[y]>=dfn[x])//发现了割点
            {
                flag++;
                ans[x]+=size[y]*(n-size[y]);//加上y儿子连通块带来的贡献
                sum+=size[y];//这里是统计儿子连通块总节点数
                if (x!=root || flag>1)//是割点
                    cut[x]=true;
            }
        }
        else
            low[x]=min(low[x],dfn[y]);//更新
    }
    if (cut[x])//是割点
        ans[x]+=(n-sum-1)*(sum+1)+(n-1);//非儿子连通块的贡献+自身节点贡献
    else
        ans[x]=2*(n-1);//不是割点
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    memset(cut,false,sizeof(cut));//刚开始都不是割点
    for(int i=1; i<=m; i++)
    {
        int a,b;
        scanf("%lld%lld",&a,&b);
        if (a==b)//无用边
            continue;
        add_edge(a,b);
        add_edge(b,a);
    }
    root=1;//根节点为1
    Tarjan(1);
    for(int i=1; i<=n; i++)
        printf("%lld\n",ans[i]);
    return 0;
}