BLO-Blockade-割点

洛谷P3469 [POI2008]BLO-Blockade

题目大意

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

思路

这道题首先考虑的便是和求割点相关；

对于每个割点，以下称当这个点被删除时，当前连通块分裂出的几个连通块为“被割集”，记第 i 个被割集的元素数量为 $c_i$ ；

对于每个节点，其造成的影响 $brk[i]=(n-1)*2+\sum(n-1-c_i)c_i$ ；对于非割点，影响仅有前一项；

在判断割点的整个dfs过程中，记以节点 i 为根的dfs树元素数量为$ctp[i]$ ，满足low[to] >= dfn[u]的子节点显然有 $c_j=ctp_{to}$ ，造成的影响是 $(n-1-c_j)c_j$ ，即每个被割集和整个图的其他部分均被分离；

当然，对于每个割点，还有一个特殊的被割集，即为包含该割点的父节点的被割集，记为 $c_0$ 。有 $c_0=n-1-\sum_{j=1}c_j$ ，影响量同上；

实际实现中，并不需要特判割点计算 $c_0$ ，对于非割点，影响量为0；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 1e8;
vector<int> rod[N]; //存路
int dfn[N], dc = 1; //dfs存储dfs入序，dc用于分配dfs序
int low[N];         //low存储节点下子树经过一次边所连接的最小dfs序
int cut[N];         //cut存储该点是否为割点
ll n;
ll brk[N];          //brk存储该点的答案
ll ctp[N];			//ctp存储dfs树中，以该点为根的子树大小
void dfs(int u, int r)
{
    low[u] = dfn[u] = dc++;
    cut[u] = (u == r) ? 0 : 1;
    brk[u] = (n - 1) * 2;
    ctp[u] = 1;
    ll tmp = 0, stp = 0;
    for (int j = 0; j < rod[u].size(); j++)
    {
        int to = rod[u][j];
        if (!dfn[to])
        {
            dfs(to, r);
            low[u] = min(low[u], low[to]);
            ctp[u] += ctp[to];
            if (low[to] >= dfn[u])
                cut[u]++, tmp += ctp[to] * (n - ctp[to] - 1), stp += ctp[to];
        }
        else
        {
            low[u] = min(low[u], dfn[to]);
        }
    }
    brk[u] += tmp + (n - stp - 1) * stp;
}
int main()
{
    int m, a, b;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &a, &b);
        rod[a].push_back(b);
        rod[b].push_back(a);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; i++)
    {
        printf("%lld\n", brk[i]);
    }
    return 0;
}

ED

\