题目链接
题意：一张无向图，把第$i$个点关联的所有边去掉，求无向图中有多少个点对不连通。
题解：
如果割的不是割点，那么总答案是$2\times (n-1)$.
如果是割点，要分别考虑每个子树的贡献.
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N = 1e5 + 10, M = 5e5 + 10; int head[N], ver[M * 2], Next[M * 2]; int dfn[N], low[N], Size[N]; ll ans[N]; bool cut[N]; int n, m, tot, num; ///时间戳号 void add(int u, int v) { ver[++tot] = v, Next[tot] = head[u], head[u] = tot; } void tarjan(int u) { dfn[u] = low[u] = ++num; Size[u] = 1; int flag = 0, sum = 0; for(int i = head[u]; i; i = Next[i]) { int v = ver[i]; if(!dfn[v]) { tarjan(v); Size[u] += Size[v]; low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) { flag++; ans[u] += (ll)Size[v] * (n - Size[v]); sum += Size[v]; if(u != 1 || flag > 1) cut[u] = true; } } else low[u] = min(low[u], dfn[v]); } if(cut[u]) ans[u] += (ll)(n - sum - 1) * (sum + 1) + (n - 1); else ans[u] = 2 * (n - 1); } int main() { scanf("%d %d", &n, &m); tot = 1; for(int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); if(u == v) continue; add(u, v), add(v, u); } tarjan(1); for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]); return 0; }
原文：https://www.cnblogs.com/wangwangyu/p/9671083.html
