蒟蒻对了但有个有个老师都没解决的问题

P8436 【模板】边双连通分量

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 说得好


|