求助 关于tarjan
  • 板块灌水区
  • 楼主CuSO4_and_5H2O
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/7/6 08:59
  • 上次更新2023/10/27 21:46:40
查看原帖
求助 关于tarjan
231946
CuSO4_and_5H2O楼主2022/7/6 08:59
void tarjan(int x)
{
	vis[x]=1;
	sta.push(x);
	dfn[x]=low[x]=++wuy;
	for(int i=0;i<vec[x].size();i++)
	{
		int nex=vec[x][i];
		if(!dfn[nex]){
			tarjan(nex);
			low[x]=min(low[x],low[nex]); 
		} else if(vis[nex]) low[x]=min(low[x],dfn[nex]); 
	}
	if(dfn[x]==low[x]){
		jis++;
		dis[jis]=a[x];
		while(sta.top()!=x)
		{
			dis[jis]+=a[sta.top()];
			b[sta.top()]=jis;
			vis[sta.top()]=0;
			sta.pop();
		}
		vis[sta.top()]=0;
		b[sta.top()]=jis;
		sta.pop();
	}
}

else if(vis[nex]) low[x]=min(low[x],dfn[nex]); 

的 dfn[nex]改成low[nex]也是对的,但是在割点操作中必须是dfn[nex]这两个有什么区别,或者是说为什么会这样。

目前个人理解(可能肯定有错)

low[nex]指的是这个点能到达的最老的祖先,在割点中这样操作计算机会认为当前点能到达low[nex],但是实际上有可能不可以,只能通过其他节点中转才可以到达,所以割点只能写dfn[nex],但是我不理解为什么tarjan两者都行,求解答

2022/7/6 08:59
加载中...