Luogu P3469 [POI2008]BLO-Blockade

YorkWu

March 12, 2019

1161 views

No comments

155 words

OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P3469 "题目链接")

#### 题目大意

给定一张无向图，求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y。

#### 输入

第1行：N, M （1<=N<=100000, 1<=M<=500000） 第2~M+1行 X Y 表示X与Y中有一条边。

#### 输出

共N行，每行一个正整数代表如果去掉第i个点有多少个不能到大的点对。

* * *

#### 代码如下
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int SIZE=500009;
    struct Edge{
        int to,next;
    }e[2*SIZE];
    int head[100010],tot,num,dfn[100010],low[100010],n,m;
    ll ans[100009],size[100009];
    bool cut[100010];
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    
    void tarjan(int x){
        dfn[x]=low[x]=++num;
        size[x]=1;
        int cnt=0;
        ll sum=0;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(!dfn[y]){
                tarjan(y);
                size[x]+=size[y];
                low[x]=min(low[x],low[y]);
                if(low[y]>=dfn[x]){
                    cnt++;
                    ans[x]+=(ll)size[y]*(n-size[y]);
                    sum+=size[y];
                    if(x!=1||cnt>1) cut[x]=1;
                }
            }
            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);
    }
    
    int main(){
        cin>>n>>m;
        tot=1;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y) continue;
            add(x,y),add(y,x);
        }
        tarjan(1);
        for(int i=1;i<=n;i++){
            printf("%lld\n", ans[i]);
        }
        return 0;
    }
```

Last modification：March 14, 2020