给定一张无向连通图,求每个点被删除之后有多少个有序点对(x,y) (x!=y,1<=x,y<=n)满足x无法到达y;
这道题首先考虑的便是和求割点相关;
对于每个割点,以下称当这个点被删除时,当前连通块分裂出的几个连通块为“被割集”,记第 i 个被割集的元素数量为 c i c_i ci ;
对于每个节点,其造成的影响 b r k [ i ] = ( n − 1 ) ∗ 2 + ∑ ( n − 1 − c i ) c i brk[i]=(n-1)*2+\sum(n-1-c_i)c_i brk[i]=(n−1)∗2+∑(n−1−ci)ci ;对于非割点,影响仅有前一项;
在判断割点的整个dfs过程中,记以节点 i 为根的dfs树元素数量为
c
t
p
[
i
]
ctp[i]
ctp[i] ,满足low[to] >= dfn[u]
的子节点显然有
c
j
=
c
t
p
t
o
c_j=ctp_{to}
cj=ctpto ,造成的影响是
(
n
−
1
−
c
j
)
c
j
(n-1-c_j)c_j
(n−1−cj)cj ,即每个被割集和整个图的其他部分均被分离;
当然,对于每个割点,还有一个特殊的被割集,即为包含该割点的父节点的被割集,记为 c 0 c_0 c0 。有 c 0 = n − 1 − ∑ j = 1 c j c_0=n-1-\sum_{j=1}c_j c0=n−1−∑j=1cj ,影响量同上;
实际实现中,并不需要特判割点计算 c 0 c_0 c0 ,对于非割点,影响量为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;
}
\