关于tarjan递归求点双联通分量
  • 板块学术版
  • 楼主little_kongbai
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/7/17 08:21
  • 上次更新2023/10/27 19:56:44
查看原帖
关于tarjan递归求点双联通分量
232205
little_kongbai楼主2022/7/17 08:21

代码A:

			if(!dfn[v]){
				tarjan(v);
				low[u]=min(low[u],low[v]);
				if(dfn[u]<=low[v]){
					++ans;int t;
					do{
						t=s.top();s.pop();
						vt[ans].push_back(t);
					}while(t!=v);
					vt[ans].push_back(u);
				}
			}else low[u]=min(low[u],dfn[v]);

代码B:

if(dfn[v])low[u]=min(low[u],dfn[v]);
			else{
				tarjan(v);
				low[u]=min(low[u],low[v]);
				if(dfn[u]<=low[v]){
					++ans;
					while(s.top()!=u){
						int t=s.top();s.pop();
						vt[ans].push_back(t);
					}
					vt[ans].push_back(u);
				}
			}

其他部分代码相同,两份代码出自不同的教练。但代码A全部AC,代码B基本全WA,主要区别就在于存双联通分量的方式,求大佬来解答下这两种写法有什么区别,为什么代码B会全WA?

2022/7/17 08:21
加载中...