本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
题意
给出一张有\(n\)个点，\(m\)条边的无向连通图，问对于每个节点\(i\)，去掉与\(i\)相连的所有边后，有多少对有序点对\((x,y)\)不再连通。
分析
根据割点的定义可知，若\(i\)不为割点，则只有剩下的\(n-1\)对点不与\(i\)联通，答案为\(2(n-1)\)。
若\(i\)为割点，则原图一定被分为两个或两个以上的连通块，应该计算出这些连通块的大小，两两相乘再相加作为答案。
不妨从DFS搜索树的角度来思考：
设在以\(u\)为根的子树上有\(p\)个节点\(v_1,v_2,\cdots,v_p\)满足\(dfn[i]\leq low[v_i](1\leq i\leq p)\)。
因为任何一棵以\(v_i\)为根的子树在删除与\(i\)相连的所有边后一定不与其他连通块连通（可画图理解），
所以，只可能有以下三种情况的连通块：
- 点\(u\)本身
- 以\(v_1\)~\(v_p\)为根的子树中的节点构成的\(t\)个连通块
- 若\(u\)不为搜索树的根，则还会有剩下的所有节点构成一个连通块
因此可以在跑tarjan的同时计算出每棵子树的大小\(siz\)，最终答案为
\[\sum^p_{i=1}(siz[v_i]\times(n-siz[v_i]))+1\times (n-1)+\left(n-1-\sum^p_{i=1}siz[v_i]\right)\left(1+\sum^p_{i=1}siz[s_i]\right)
\]
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 100005
#define M 500005
#define int long long
using namespace std;
struct Edge{
int nxt,to;
}e[M<<1];
int n,m,cnt,head[N];
void addedge(int x,int y)
{
++cnt;
e[cnt].nxt=head[x];
e[cnt].to=y;
head[x]=cnt;
}
int root=1,tot,dfn[N],low[N],cut[N],siz[N],ans[N];
void tarjan(int u)
{
int flag=0,sum=0;
dfn[u]=low[u]=++tot;siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
siz[u]+=siz[v];
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
flag++;
ans[u]+=siz[v]*(n-siz[v]);
sum+=siz[v];
if(u!=root||flag>1)
cut[u]=1;
}
}
else low[u]=min(low[u],dfn[v]);
}
if(cut[u]) ans[u]+=((n-1)+(n-1-sum)*(1+sum));
else ans[u]=2*(n-1);
// 这里并没有判断每个满足low[v]>=dfn[u]的节点是否为割点，而是最后统一处理
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1,x,y;i<=m;i++){
scanf("%lld%lld",&x,&y);
if(x!=y) addedge(x,y),addedge(y,x);
}
tarjan(root);
for(int i=1;i<=n;i++)
printf("%lld\n",ans[i]);
return 0;
}
结语
在图论的连通性问题中，经常要从搜索树的角度来分析并解决问题
