题目大意

「POI 2008」BLO（BZOJ 1123）

给定一个 $n$ 个点 $m$ 条边的无向图，问删去每个点的所有邻边以后图中有多少对结点（有序数对）不联通。

数据范围： $n \le 10^5, m \le 5 \times 10^5$ 。

思路分析

首先删去某个点的邻边之后，它和其他所有点都不联通，所以预先把答案加上 $2n - 2$ 。

根据割点的定义，只有删掉割点才会使图有不联通。对于每一个结点 $u$ ，我们看它会使那些结点不联通。考虑求割点的过程，如果一个相邻的点 $v$ 满足 $\text{low}(v) == \text{dfn}(u)$ ，那么删掉 $u$ 就切断了 $v$ 的子树，也就是 $v$ 的子树与上面不联通了。我们对于每个点维护它在 DFS 树上子树的大小，然后每次找到一组 $\text{low}(v) == \text{dfn}(u)$ 我们就将 $v$ 子树内部的点数乘上当前删掉 $u$ 后已经不和 $u$ 父亲联通的点数 $s$ 的值贡献到 $u$ 的答案中，然后再把 $s$ 加上 $v$ 的子树大小。最后，我们再把答案加上 $s$ 乘上 $n - s - 1$ 的值（表示 $u$ 下面的点和 $u$ 上面的点不联通的组数）即可。不要忘记这题求的是有序数对，所以答案要乘以 $2$ ；并且根结点是否是割点也是需要特判的。

时间复杂度 $O(n + m)$ 。

代码实现

1	#include <cstdio>
2	#include <vector>
3	#include <algorithm>
4	using namespace std;
5
6	const int maxn = 1e5;
7	typedef long long ll;
8	int n, m, tm, sz[maxn + 3], dfn[maxn + 3], low[maxn + 3];
9	vector<int> G[maxn + 3];
10	ll ans[maxn + 3];
11	bool cut[maxn + 3];
12
13	void add(int u, int v) {
14	G[u].push_back(v);
15	}
16
17	void tarjan(int u, bool is_rt = true) {
18	dfn[u] = low[u] = ++tm, sz[u] = 1;
19	int cnt = 0, sum = 0;
20	for (int i = 0, v; i < G[u].size(); i++) {
21	v = G[u][i];
22	if (!dfn[v]) {
23	tarjan(v, false);
24	low[u] = min(low[u], low[v]);
25	sz[u] += sz[v], cnt++;
26	if (low[v] == dfn[u]) {
27	ans[u] += 1ll * sum * sz[v];
28	sum += sz[v];
29	cut[u] = true;
30	}
31	} else {
32	low[u] = min(low[u], dfn[v]);
33	}
34	}
35	if (is_rt) {
36	cut[u] = cnt >= 2;
37	}
38	ans[u] += 1ll * sum * (n - sum - 1);
39	if (!cut[u]) {
40	ans[u] = 0;
41	}
42	ans[u] = 2 * (ans[u] + n - 1);
43	}
44
45	int main() {
46	scanf("%d %d", &n, &m);
47	for (int i = 1, u, v; i <= m; i++) {
48	scanf("%d %d", &u, &v);
49	add(u, v), add(v, u);
50	}
51	tarjan(1);
52	for (int i = 1; i <= n; i++) {
53	printf("%lld\n", ans[i]);
54	}
55	return 0;
56	}