关于 tarjan
  • 板块学术版
  • 楼主wurang
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/1 14:49
  • 上次更新2025/7/1 14:51:29
查看原帖
关于 tarjan
836786
wurang楼主2025/7/1 14:49

这篇文章中提到 dfndfnlowlow 的计算方式:

void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	for(auto y : G[u])
	{
		if(!dfn[y])
		{
			tarjan(y,u);
			low[u]=min(low[u],low[y]);
		}
		else if(y!=fa)low[u]=min(low[u],dfn[y]);
	}
}

但这里如果u与y有重边,是否该改为:

void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	for(auto y : G[u])
	{
		if(!dfn[y])
		{
			tarjan(y,u);
			low[u]=min(low[u],low[y]);
		}
		else if(y!=fa)low[u]=min(low[u],dfn[y]);
        if(y == fa) fa = -1;
	}
}
2025/7/1 14:49
加载中...