求助30分
查看原帖
求助30分
310999
TomGreen楼主2023/3/1 22:47

自己写的一直30分,同学帮我把计算答案的那部分改到tarjan里就A了,蒟蒻想请教一下为什么

改之前

void tarjan(int x){
	dfn[x]=low[x]=++nw;
	int ch=0;
	for(int i=head[x];i!=0;i=e[i].nxt){
		int to=e[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[x]=min(low[x],low[to]);
			ch++;
			if(ch>1&&x==1) vis[x]=true;
			else if(x!=1&&dfn[x]<=low[to]) vis[x]=true;
		}
		else low[x]=min(low[x],dfn[to]);
	}
}
void calc(int x){
	if(!vis[x]){
		ans[x]=2*(n-1);
	}
	siz[x]=1;
	v[x]=true;
	for(int i=head[x];i!=0;i=e[i].nxt){
		int to=e[i].to;
		if(v[to]) continue;
		v[to]=true;
		calc(to);
		siz[x]+=siz[to];
		if(vis[x]){
			ans[x]+=siz[to]*(n-siz[to]-1);
			//cout<<"qaq "<<ans[x]<<endl;
		}
	}
	if(vis[x]){
		ans[x]+=(n-siz[x])*(siz[x]-1);
		ans[x]+=2*(n-1);
	}
}

改之后
void tarjan(int x){
	dfn[x]=low[x]=++nw;
	int ch=0, sum = 0;
	siz[x]=1;
	for(int i=head[x];i!=0;i=e[i].nxt){
		int to=e[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[x]=min(low[x],low[to]);
			ch++;
			siz[x]+=siz[to];
			if(dfn[x]<=low[to]) {
				vis[x]=true;
				sum+=siz[to]; 
				ans[x]+=siz[to]*(n-siz[to]);
			}
			if(vis[x]){
				//cout<<"qaq "<<ans[x]<<endl;
			}
		}
		else low[x]=min(low[x],dfn[to]);
	}
	if(vis[x]){
		ans[x]+=(n-sum-1)*(sum+1);
		ans[x]+=(n-1);
	} 
   else ans[x]=(n-1)*2;
}
2023/3/1 22:47
加载中...