题目大意
给出一张无向图，要求输出分别删除某个点相连的边后，无向图中有多少个有序点对满足(x)和(y)不连通
问题求解
删掉一个点是否连通，自然而然就想到了割点，如果这个点是割点，那么删掉边后其他(n-1)的点都是连通的，由于是有序点对，所以这个点的答案就是(2 imes (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] imes(n-size[s_i])}+1 imes(n-1)+(n-1-sum_{i=1}^t{size[s_k]}) imes(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
",Ans[i]);
return 0;
}