P3469 题解

题意

给出一张有\(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\)相连的所有边后一定不与其他连通块连通（可画图理解），
所以，只可能有以下三种情况的连通块：

1. 点\(u\)本身
2. 以\(v_1\)~\(v_p\)为根的子树中的节点构成的\(t\)个连通块
3. 若\(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;
}

结语

在图论的连通性问题中，经常要从搜索树的角度来分析并解决问题