<题目链接>
以下内容转自李煜东的《算法竞赛进阶指南》
题目大意：
现在给定一张连通的无向图，不包含重边。现在输出$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+5, M = 5e5+5; struct Edge{ int to,nxt; }edge[M<<1]; 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]=1; int flag=0,sum=0; 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!=1 || flag>1)cut[u]=true; } }else low[u]=min(low[u],dfn[v]); } if(cut[u])ans[u]+=(ll)(sum+1)*(n-sum-1)+(n-1); //父亲方向的点与其它点构成的有序对 以及 i节点独自与其它节点构成的有序对 else ans[u]=2*(n-1); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); addedge(u,v);addedge(v,u); } Tarjan(1); //因为这是无向图，并且所有的点连通 for(int i=1;i<=n;i++) printf("%lld ",ans[i]); }
2019-03-01