【洛谷 P3469】[POI2008]BLO-Blockade（割点）

题目链接

题意：一个无向联通图，求删去每个点及其所有边后有多少有序点对的连通性发生了变化。

Tarjan求割点的例题。。

如果当前点不是割点，那么它对整个图的连通性不产生影响，只有自己与其他\(n-1\)个点的连通性发生了变化，故答案为\((n-1)\times2\)。

如果当前点是割点，那么除了自身外，它所连接的所有连通块和其他连通块之间的连通性都发生了变化，故答案为:

设\(size[u]\)表示以u为根的连通块的大小，与当前点相连的共有\(k\)个连通块，

\[ans=\sum_{i=1}^{k}[size[i]\times(n-size[i])]+(n-1)+(n-1-\sum_{i=1}^{k}size[i])\times(\sum_{i=1}^{k}size[i]+1)
\]

#include <cstdio>

#include <algorithm>

using std::min;

const int MAXN = 100010;

const int MAXM = 500010;

struct Edge{

    int next, to;

}e[MAXM << 1];

int num, head[MAXN];

inline void Add(int from, int to){

    e[++num] = (Edge){ head[from], to };

    head[from] = num;

}

int dfn[MAXN], low[MAXN], size[MAXN];

long long ans[MAXN];

int id, n, m;

void Tarjan(int u){

    dfn[u] = low[u] = ++id;

    size[u] = 1;

    int flag = -1, sum = 0;

    for(int i = head[u]; i; i = e[i].next){

       if(!dfn[e[i].to]){

         Tarjan(e[i].to);

         size[u] += size[e[i].to];

         low[u] = min(low[u], low[e[i].to]);

         if(low[e[i].to] >= dfn[u]){

           ans[u] += (long long)size[e[i].to] * (n - size[e[i].to]);

           sum += size[e[i].to];

           if(u != 1 || ++flag)

             flag = 100000;

         }

       }

       else low[u] = min(low[u], dfn[e[i].to]);

    }

    if(flag != 100000) ans[u] = (n - 1) << 1;

    else ans[u] += (long long)(n - sum - 1) * (sum + 1) + n - 1;

}

int a, b;

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++i){

       scanf("%d%d", &a, &b);

       Add(a, b); Add(b, a);

    }

    Tarjan(1);

    for(int i = 1; i <= n; ++i)

       printf("%lld\n", ans[i]);

    return 0;

}

巴特西

【洛谷 P3469】[POI2008]BLO-Blockade（割点）

最新文章

热门文章