[POI2008]BLO-Blockade--Tarjan割点

本文主要是介绍[POI2008]BLO-Blockade--Tarjan割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Luogu 3469ACwing 365

题目分析：

对于一个点 $u$ ,分此点是否为割点进行讨论：
若 $u$ 不是割点，则将此点删除，其他 $n - 1$ 个点仍联通，则 $u$ 与其他 $n - 1$ 个点不连通，由于求的是有序点对 $(x, y)$ ,则 $a n s [u] = 2 * (n - 1)$
若 $u$ 为割点， $u$ 有 $t$ 个 $v$ ,则删除 $u$ 之后，最多产生 $t + 2$ 个连通块：
$u$ 自己为一个连通块
$t$ 个 $v$ 各自为一个连通块
其他的节点构成一个连通块
对于 $u$ 的 $v$ ，若 $dfn[u]<=low[v],sum=\sum{size[v]}$
$ans[u]=size[v_1]*(n-size[v_1])+size[v_2]*(n-size[v_2])+......+size[v_t]*(n-size[v_t])+(n-sum-1)*(sum+1)$

Code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define maxm 500010int n,m,size=0,head[maxn],f[maxn],cnt=0,dfn[maxn],low[maxn];
long long ans[maxn];
bool co[maxn];
struct edge {int v,nxt;
}e[maxm<<1];inline void init_() {freopen("a.txt","r",stdin);
}inline int read_() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}inline void add_(int u,int v) {e[++size].v=v;e[size].nxt=head[u];head[u]=size;
}inline void clean_() {memset(co,false,sizeof(co));memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));
}void Tarjan_(int u) {dfn[u]=low[u]=++cnt;f[u]=1;ans[u]=0;int flag=0,sum=0;for(int i=head[u];~i;i=e[i].nxt) {int v=e[i].v;if(!dfn[v]) {Tarjan_(v);low[u]=min(low[u],low[v]);f[u]+=f[v];if(dfn[u]<=low[v]) {++flag;ans[u]+=(long long) f[v]*( (long long) n-f[v] );sum+=f[v];if(u!=1||flag>1) co[u]=true;}}else low[u]=min(low[u],dfn[v]);}if(co[u]) {ans[u]+=(long long) n-1;ans[u]+=(long long) ( (long long) n-sum-1 ) * ( (long long) sum+1 );}else {ans[u]=(long long) 2 * ( (long long) n-1 );}
}void readda_() {n=read_();m=read_();clean_();int x,y;for(int i=1;i<=m;++i) {x=read_();y=read_();if(x==y) continue;add_(x,y);add_(y,x);}Tarjan_(1);for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
}int main() {init_();readda_();return 0;
}