B城
C++ 代码
/*
根据割点的定义,若节点 i 不是个点,则把节点 i 关联的所有边去掉之后,只有 i 与其他 n - 1 个节点不连通,
而其他 n - 1 个节点之间是连通的。注意:题目求的是有序点对,即 (x, y) 和 (y, x) 算不同的点对,故此时
答案是 2 * (n - 1)
若节点 i 是割点,则把节点 i 关联的所有边去掉之后,图会分成若干个连通块,我们应该求出这些连通块的大小,
两两相乘再相加。
假设节点 i 的子节点集合中,有 t 个子节点 s[k],满足 dfn[i] <= low[s[k]],那么删除节点 i 关联的所有边后,
无向图最多分成 t + 2 个连通块,情况一共分为 3 类:
1. 节点 i 自身单独构成一个连通块
2. 有 t 个连通块,分别由搜索树上以 s[k] 为根节点的子树中的节点构成
3. 还可能有一个连通块,由除了上述节点之外的所有点构成
因此可以在 Tarjan 算法求割点的过程中顺便求一下 cnt[x],即以节点 x 为根节点的子树中的节点个数。
因此删掉割点 i 之后,不连通的有序点对数量为:
cnt[s[1]] * (n - cnt[s[1]]) + cnt[s[2]] * (n - cnt[s[2]]) + ... + cnt[s[n]] * (n - cnt[s[n]]) +
1 * (n - 1) + (n - 1 - sum(cnt[s[k]])) * (1 + sum(cnt[s[k]])) (1 <= k <= t)
综上所述,即为本题算法
*/
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010, M = 1000010;
int n, m;
int h[N], e[M], ne[M], idx; //邻接表
int dfn[N], low[N], timestamp; //时间戳、能到达的最近时间戳、当前用到的时间戳编号
int cnt[N]; //记录以节点 i 为根节点的子树中的节点个数
LL res[N]; //记录每个节点 i 周边所有边去掉之后不连通的有序点对数量
bool cut[N]; //记录每个节点 i 是不是割点
void add(int a, int b) //添加边
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp; //更新时间戳、能到达的最近时间戳
cnt[u] = 1; //当前子树中节点个数为1
int s = 0, sum = 0; //s 记录删去当前节点周围所有边后剩下的连通块数量,sum 记录 s 个节点子树中的节点总数
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
cnt[u] += cnt[j]; //累加节点数量
low[u] = min(low[u], low[j]); //更新能到达的最近时间戳
if(dfn[u] <= low[j])
{
s++;
res[u] += (LL)cnt[j] * (n - cnt[j]); //累加有序点对数量
sum += cnt[j]; //累加 s 个节点子树中的节点总数
if(u != 1 || s > 1) cut[u] = true; //u 节点是割点
}
}
else low[u] = min(low[u], dfn[j]); //更新能到达的最近时间戳
}
if(cut[u]) res[u] += (LL)(n - 1 - sum) * (1 + sum) + (n - 1); //计算有序点对数量
else res[u] = 2 * (n - 1);
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h); //初始化邻接表
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a); //无向边
}
tarjan(1);
for(int i = 1; i <= n; i++) printf("%lld\n", res[i]);
return 0;
}