不是很懂/ll
查看原帖
不是很懂/ll
483928
Z1qqurat楼主2023/10/19 19:37

额,不是说在弹栈的时候,不能把那个树根(割点)弹掉吗,因为可能多个点双共用这个点,但是下面这两种写法有什么区别吗???

WA:

if(low[v] >= dfn[u]) {                
                if(siz > 1 || u != rt) cut[u] = 1;
                cnt++;
                while(!s.empty()) {
                    int cur = s.top();
                    dcc[cnt].emplace_back(cur);
                    if(cur == u) break;
                    s.pop();
                }
            }

AC:

if(!dfn[v]) {
            tarjan(v, rt), low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {                
                cnt++;
                while(!s.empty()) {
                    int cur = s.top(); s.pop();
                    dcc[cnt].emplace_back(cur);
                    if(cur == v) break;                
                }
                dcc[cnt].emplace_back(u);
            }
        }

明明只是弹栈的时候用了不同的判法啊qwq

2023/10/19 19:37
加载中...