<题目链接>
以下内容转自李煜东的《算法竞赛进阶指南》
题目大意：
现在给定一张连通的无向图，不包含重边。现在输出$n$个整数，表示将第$i$个节点的所有与其它节点相关联的边去掉之后(不去掉$i$节点本身)，无向图中有多少个有序对$(u,v)$，满足$u,v$不连通。
解题分析：
首先，很明显，$i$节点是需要分成割点和非割点来进行讨论的。
对于非割点i来说，去除$i$周围的所有边之后，只有$i$点和其它$n-1$个点不连通，所以增加的有序对为$2*(n-1)$个。
对于割点$i$来说，假设在搜索树上，节点i有$t$个子树，则至多能够够分成$t+2$个连通块，每个连通块的节点构成情况为：
1.节点$i$独自构成一个连通块
2.有$t$个连通块，分别由搜索树上$i$的$t$个子树的所有节点分别构成
3.还有除上述所有节点之外的点构成(比如在搜索树上，$i$节点父亲方向的所有节点)
割点有序对的所有情况就能够依据上面几种情况求出，这里就不再进行赘述。
割点的判定法则：
u是割点当且仅当搜索树上存在的一个子节点v,满足：$low[v]>=dfn[u]$
特别地，如果u是搜索树上的根节点，则u是割点当且仅当存在至少两个子节点满足上述条件。
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 1e5+, M = 5e5+;
struct Edge{
int to,nxt;
}edge[M<<]; int n,m,cnt,tot,head[N],dfn[N],low[N],sz[N];
bool cut[N];
ll ans[N]; void addedge(int u,int v){
edge[++cnt].to=v,edge[cnt].nxt=head[u];
head[u]=cnt;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;sz[u]=;
int flag=,sum=;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
sz[u]+=sz[v];
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){ //如果满足割点的条件
flag++;
ans[u]+=(ll)(sz[v])*(n-sz[v]); //v所在的连通分量与其它所有点构成的有序对数量
sum+=sz[v];
if(u!= || flag>)cut[u]=true;
}
}else low[u]=min(low[u],dfn[v]);
}
if(cut[u])ans[u]+=(ll)(sum+)*(n-sum-)+(n-); //父亲方向的点与其它点构成的有序对 以及 i节点独自与其它节点构成的有序对
else ans[u]=*(n-);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
Tarjan(); //因为这是无向图，并且所有的点连通
for(int i=;i<=n;i++)
printf("%lld\n",ans[i]);
}
2019-03-01