[Luogu 3469] [POI2008]BLO-Blockade

Posted on | Edited on | In , | Views:

题目链接

Luogu 3469

题目大意

给定一张$n$个点$m$条边的联通无向图，问删除每个点后有多少点不连通。
$n\le 10^5$，$m\le 5*10^5$

做法

如果我们能够快速知道每个点被删除后，剩下的每个联通块的大小就可以算出答案了。
具体做法：对每个节点记录一个$now$，一个$ans$，表示这个节点当前联通块大小的和，找到一个新的联通块后$ans+=now*size,now+=size$
那么我们就用$tarjan$求割点，每当一个点作为割点的时候统计答案。
用$size_i$表示$i$号点目前所在联通块的大小。
$now_i,ans_i$表示上述做法中的$now,ans$
在$tarjan$求割点的时候，如果发现$low[v]>=dfn[u]$，说明$v$所在的联通块在割掉$u$这个点之后是一个独立的联通块，那么$ans[u]+=now[u]*size[v],now[u]+=size[v]$。
但是别忘了最后还要加上最后一个联通块，这个联通块是在$tarjan$我之前遍历的那个联通块。
所以$ans[u]+=now[u]*(n-now[u]-1)$
还有就是我这个点被删掉了，所以我不能走到其他的任意点$ans[u]+=n-1$
由于点对是无序点对，$ans[u]*=2$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
#define M (500005)
using namespace std;
int n,m,tot,cnt,x,y;
int head[N],nxt[M<<1],son[M<<1],now[N],size[N],dfn[N],low[N];
LL ans[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline void add(int x,int y){
    son[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    size[u]=1;
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (!dfn[v]){
            tarjan(v);
            size[u]+=size[v];
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]){
                ans[u]+=1ll*now[u]*size[v];
                now[u]+=size[v];
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int main(){
    read(n),read(m);
    for (int i=1;i<=m;i++){
        read(x),read(y);
        add(x,y),add(y,x);
    }
    tarjan(1);
    for (int i=1;i<=n;i++) ans[i]+=1ll*now[i]*(n-now[i]-1);
    for (int i=1;i<=n;i++) ans[i]=(ans[i]+(n-1))*2;
    for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}