关于Tarjan
  • 板块学术版
  • 楼主CH_mengxiang
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/11/23 09:28
  • 上次更新2023/10/27 01:52:08
查看原帖
关于Tarjan
190485
CH_mengxiang楼主2022/11/23 09:28

几个月前学的,板子会打,但是到现在都不清楚某些地方的if到底要不要加。看题解每个人写的都不一样。

比如P2860这道题

void tarjan(int u)
{
	dfn[u]=low[u]=++num,s[++top]=u;
	for (int e=fir[u];e;e=nxt[e])
	{
		if (vis[e]) continue;
		vis[e]=vis[e^1]=1;//有的加了有的没加
		int v=to[e];
		if (!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);//看很多人把if删了?
	}
	if (dfn[u]==low[u])
	{
		co[u]=++col;
		while (s[top]!=u) co[s[top--]]=col;
		top--;
	}
}

有没有人能稍微清楚地解释一下,谢谢!

2022/11/23 09:28
加载中...