题目大意
给出一张无向图,要求输出分别删除某个点相连的边后,无向图中有多少个有序点对满足\(x\)和\(y\)不连通
问题求解
删掉一个点是否连通,自然而然就想到了割点,如果这个点是割点,那么删掉边后其他\(n-1\)的点都是连通的,由于是有序点对,所以这个点的答案就是\(2 \times (n-1)\)
对于不是割点的点,需要求出删除后各连通块的大小,相乘的和就是答案,然后思考如何快速求出,在搜索树上,节点\(i\)的子节点集合中,有\(t\)个点\(s_1,s_2,...,s_k\)满足割点判定条件,\(dfn[i]≤low[s_k]\),于是,删除\(i\)关联的所有边后,无向图会分成至多\(t+2\)个连通块因为
-
节点\(i\)自身是一个连通块
-
有\(t\)个连通快,分别由搜索树上以\(s_k(1≤k≤t)\)为根的子数中的节点构成
-
还可能有一个连通块,除了由上述节点之外的所有节点构成
所以记下搜索树中子树的大小\(size[x]\),显然答案就表示成
\[\sum_{i=1}^t{size[s_i]\times(n-size[s_i])}+1\times(n-1)+(n-1-\sum_{i=1}^t{size[s_k]})\times(1+\sum_{i=1}^t{size[s_k]}) \]代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100005,maxe=1000005;
int lnk[maxn],nxt[maxe],son[maxe],cnt=1,num;
int dfn[maxn],low[maxn],size[maxn];
int N,M;
LL Ans[maxn];
bool cut[maxn];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void add_e(int x,int y){son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;}
void tarjan(int x){
dfn[x]=low[x]=++num;size[x]=1;
int flg=0,sum=0;
for(int j=lnk[x];j;j=nxt[j]){
if(!dfn[son[j]]){
tarjan(son[j]);
size[x]+=size[son[j]];
low[x]=min(low[x],low[son[j]]);
if(dfn[x]<=low[son[j]]){
flg++;
Ans[x]+=(LL)size[son[j]]*(N-size[son[j]]);
sum+=size[son[j]];
if(x!=1||flg>1)cut[x]=1;
}
}
else low[x]=min(low[x],dfn[son[j]]);
}
if(cut[x])
Ans[x]+=(LL)(N-sum-1)*(sum+1)+(N-1);
else
Ans[x]=2*(N-1);
}
int main(){
freopen("P3469.in","r",stdin);
freopen("P3469.out","w",stdout);
N=read();M=read();
for(int i=1;i<=M;i++){
int x=read(),y=read();
if(x==y)continue;
add_e(x,y);add_e(y,x);
}
tarjan(1);
for(int i=1;i<=N;i++)
printf("%lld\n",Ans[i]);
return 0;
}