BZOJ1123 tarjan求割点
考虑删除的点为割点和非割点:设总共有n个点,第i个点断开;
- 非割点,那么剩下的n-1个点都是连通的,故只有i点与别的点都不连通,那么此时的有序点对为:2*(n-1);
- 割点,那么去掉这些与i点相连的边后,会划分成若干个连通块,若我们已知每个连通块内的点数,那么将他们两两相乘再相加即为有序点对;
好的,这时问题转化为了如何快速的求出去掉i点后,各个连通块内的点个数。
我们其实可以将连通块的种类分为3种,其一是i点自身,二是除了i点的其他割点构成的连通块,三是除去i,所有割点以外,剩下的所有点构成的块。
上图: --来源《算法竞赛进阶指南》-李煜东著;
其中SIZE[S1]*(n-SIZE[S1])表示该连通块到其他别的点都是不连通的,1*(n-1)为那个去掉的第i个点到其他点不连通,
最后那个()*()就是除了割点,除了被去掉的这个点构成的点的集合,到割点及i点的不连通。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxm=1e6+7;
const int maxn=1e5+7;
struct Edge{
int v,next;
}edge[maxm];
int head[maxn],top;
void init(){
top=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v){
edge[top].v=v;
edge[top].next=head[u];
head[u]=top++;
}
bool cnt[maxn];
int index,root;
int dfn[maxn],low[maxn];
int size1[maxn];
ll res[maxn];
int n;
void tarjan(int u){
dfn[u]=low[u]=++index;
size1[u]=1;
int f=0;
int sum=0;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(!dfn[v]){
tarjan(v);
size1[u]+=size1[v];
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
++f;
if(u!=root||f>1) cnt[u]=1;
res[u]+=1LL*size1[v]*(n-size1[v]);
sum+=size1[v];
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(cnt[u]){
res[u]+=1LL*(n-1-sum)*(sum+1)+n-1;
}
else
res[u]=2*(n-1);
}
int main(){
int m;
init();
scanf("%d%d",&n,&m);
int u,v;
while(m--){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
root=1;
tarjan(1);
for(int i=1;i<=n;++i)
printf("%lld\n",res[i]);
return 0;
}