LingHusama @ 2023-07-18 15:31:41
这是我tarjan 代码,过了的,但是想知道:
low[x]=min(low[x],dfn[to]);
(在倒数第10行)
为什么前面打和不打else都是对的,是数据问题吗?
void tarjan(int x,int fa){
++t;
dfn[x]=t;
low[x]=t;
top++;
s[top]=x;
bool f=0;//用来判重边,自环
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa&&f==0){
f=1;
continue;
}
if(!dfn[to]){
tarjan(to,x);
low[x]=min(low[x],low[to]);
}
low[x]=min(low[x],dfn[to]);
}
if(low[x]==dfn[x]){
cnt++;
while(s[top+1]!=x){
bcc[cnt].push_back(s[top]);
top--;
}
}
}
by LingHusama @ 2023-07-18 15:32:24
包括我点双模板也是一样的,这个else到底有没有必要?
by Liuxizai @ 2023-07-22 09:31:25
逻辑上说需要 else,但是你前面有 low=min(low, low)
再做一次 low=min(low, dfn)
不会对结果有任何影响。
by LingHusama @ 2023-07-28 07:46:52
@Liuxizai 感谢大佬
by Masna_Kimoyo @ 2023-08-31 17:38:23
@Liuxizai 说得好