题目大意
给定一个 $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 | |
2 | |
3 | |
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 | } |