关于tarjan求强连通分量和边双的代码的小细节
  • 板块学术版
  • 楼主expnoi
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/12/4 19:22
  • 上次更新2023/10/27 00:28:33
查看原帖
关于tarjan求强连通分量和边双的代码的小细节
378346
expnoi楼主2022/12/4 19:22

以边双为例:

		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
			{
				e[i].flag=e[i^1].flag=1;
				//cout<<u<<" "<<v<<'\n';
			}
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],low[v]);
		}

规范代码为

```cpp
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
			{
				e[i].flag=e[i^1].flag=1;
				//cout<<u<<" "<<v<<'\n';
			}
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}

但是上者也获取了ac,求强连通分量也是类似,为什么他能正确呢?

2022/12/4 19:22
加载中...