171°

Blockade(Bzoj1123)

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

 

【题前话】

    这题真的害人不浅啊!

    本蒟蒻怀着做板子题1A的心态打开这道题,结果经过了三个多小时,经历了又A又RE又WA又栈溢出的代码,终于在机房大佬的题解和讲解之下终于AC了,RE和栈溢出的原因竟是因为一个变量开了long long!必须定义时定义int,乘的时候改为long long才能A!

    本蒟蒻都惊到了,果然计算机是一个玄学的学科,对萌新真的很不友好!我到现在还是不明白,如果有路过大佬能解答我的疑惑的,在下感激不尽!(具体是哪个变量我会在题外话里写出)

 

【题解】

    首先,大家应该都知道,这道题是用TARJAN算法的。(没学过的小盆友可以去学习一发:https://www.cnblogs.com/mxrmxr/p/9715579.html)

有的人或许觉得这道题是TARJAN缩点,其实不然。这道题是用TARJAN求割点的。具体思路如下:

    打一个TARJAN模板,按照DFS树搜索,DFS返回后,判断当前点是不是割点,如果是的话,那么这个点和刚才搜索的点就是一个联通块。

那我们怎么处理有多少对点呢?

    其实很简单,就是乘法原理,相信大家都学过吧。(没学过的出门右转去语文竞赛吧

    总体思路如下:

    对于每个割点,它的儿子们肯定有至少两个联通块,如果这个割点被删除,下面的联通块都不会互通。我们定义ans[u]为这个点去掉后有多少点不能互通,我们在计算每个它下面的联通块时,把它们的大小依次乘起来(就是下面的核心代码,这里看不懂就先往下翻)。然后,再加上它儿子们的联通块的和乘以他父亲们所有点的和,(就是乘法原理啦)这样,我们的思路就基本结束了。

    上文的核心代码是怎么写的呢?如下。

if(low[v]>=dfn[u])
{
    ans[u]+=(ll)sum*size[v];
    sum+=size[v];
}

我们定义size代表以u为根的联通块大小,sum表示已经遍历的子联通块,当我们发现一个新的联通块时,要把sum的大小乘以已经遍历的(乘法原理),就是size[v]啦。这时我们又遍历了一个,所以sum要加上它。(就是size[v] 啦)

 总代码如下

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXN 1000010
#define num ch-'0'
#define ll long long
void get(int &res)
{
    char ch;bool flag=0;
    while(!isdigit(ch=getchar()))
        (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getchar());res=res*10+num);
    (flag)&&(res=-res);
}
int n,m,tot=0,cnt;
int hea[MAXN],nex[MAXN<<4],to[MAXN<<4];
int dfn[MAXN],low[MAXN],size[MAXN];
ll ans[MAXN<<2];
inline void add(int a,int b)
{
    to[++tot]=b;
    nex[tot]=hea[a];
    hea[a]=tot;
}    
inline void tarjan(int u)
{
    int sum=0;
    dfn[u]=low[u]=++cnt;
    size[u]=1;
    for(int i=hea[u];i;i=nex[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            size[u]+=size[v];
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                ans[u]+=(ll)sum*size[v];
                sum+=size[v];
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    ans[u]+=(ll)sum*(n-sum-1);
}
int main()
{
    get(n),get(m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        get(a),get(b);
        add(a,b);add(b,a);
    }
    tarjan(1);
    for(int i=1;i<=n;i++)
      printf("%lld\n",(ans[i]+n-1)<<1);
}

 

【题外话】

    在写TARJAN时,我的sum(含义如上文所讲)如果int就会WA,如果long long就会RE和栈溢出,只有先定义为int,后面乘法时改为long long才能A。

    本蒟蒻十分不解,还望请过路大神指点高明。

原文链接:https://www.cnblogs.com/mxrmxr/p/9720857.html

全部评论: 0

    我有话说: