[数据结构与算法][luogu] P3469 [POI2008]BLO-Blockade Tarjan判断割点

前言

传送门 :

思路

对于当前删除的点, 如果这个点不是割点的话,那么这个点给出的贡献就是$2?(n?1)$

否则如果是割点的话 ,删除这个点,整个图将会变成多个连通块

因此对于每一个连通块的贡献又是$sz[i]?(n?sz[i])$

因此计算即可 [判断割点传送门]

Code

const int N = 1e6+10;
int n,m;
int h[N],e[N*2],ne[N*2],idx;

ll ans[N];
int dfn[N],low[N],sz[N],tot;
int st[N];


void add(int a,int b){
	e[++idx] = b,ne[idx] = h[a] ,h[a] = idx;
}

void tarjan(int u){
	dfn[u] = low[u] = ++tot;
	sz[u] = 1;
	int flag= 0 , sum = 0;
	for(int i = h[u];i;i=ne[i]){
		int j = e[i];
		if(!dfn[j]){
			tarjan(j);
			sz[u]+=sz[j];
			low[u] = min(low[u],low[j]);
			if(low[j] >= dfn[u]){
				ans[u] += 1ll*sz[j]*(n-sz[j]);
				sum+=sz[j];
				flag ++;
				if(u!=1 || flag >1)st[u] = true;
			}
		}else low[u] = min(low[u],dfn[j]);
	}
	
	//如果是割点的话
	if(!st[u]) ans[u] = 2*(n-1);
	else ans[u]+=1ll*(n-sum-1)*(sum+1)+(n-1);
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		add(a,b);add(b,a);
	}
	tarjan(1);
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	
}

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生