题目链接
题意：一个无向联通图，求删去每个点及其所有边后有多少有序点对的连通性发生了变化。
Tarjan求割点的例题。。
如果当前点不是割点，那么它对整个图的连通性不产生影响，只有自己与其他(n-1)个点的连通性发生了变化，故答案为((n-1) imes2)。
如果当前点是割点，那么除了自身外，它所连接的所有连通块和其他连通块之间的连通性都发生了变化，故答案为:
设(size[u])表示以u为根的连通块的大小，与当前点相连的共有(k)个连通块，
[ans=sum_{i=1}^{k}[size[i] imes(n-size[i])]+(n-1)+(n-1-sum_{i=1}^{k}size[i]) imes(sum_{i=1}^{k}size[i]+1)
]
#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN = 100010;
const int MAXM = 500010;
struct Edge{
int next, to;
}e[MAXM << 1];
int num, head[MAXN];
inline void Add(int from, int to){
e[++num] = (Edge){ head[from], to };
head[from] = num;
}
int dfn[MAXN], low[MAXN], size[MAXN];
long long ans[MAXN];
int id, n, m;
void Tarjan(int u){
dfn[u] = low[u] = ++id;
size[u] = 1;
int flag = -1, sum = 0;
for(int i = head[u]; i; i = e[i].next){
if(!dfn[e[i].to]){
Tarjan(e[i].to);
size[u] += size[e[i].to];
low[u] = min(low[u], low[e[i].to]);
if(low[e[i].to] >= dfn[u]){
ans[u] += (long long)size[e[i].to] * (n - size[e[i].to]);
sum += size[e[i].to];
if(u != 1 || ++flag)
flag = 100000;
}
}
else low[u] = min(low[u], dfn[e[i].to]);
}
if(flag != 100000) ans[u] = (n - 1) << 1;
else ans[u] += (long long)(n - sum - 1) * (sum + 1) + n - 1;
}
int a, b;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i){
scanf("%d%d", &a, &b);
Add(a, b); Add(b, a);
}
Tarjan(1);
for(int i = 1; i <= n; ++i)
printf("%lld
", ans[i]);
return 0;
}