关于tarjan的访问有些疑问
  • 板块学术版
  • 楼主かわいい子
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/31 19:51
  • 上次更新2023/11/2 10:31:11
查看原帖
关于tarjan的访问有些疑问
256996
かわいい子楼主2023/10/31 19:51

void dos(int x){
    cor[x] = tot;
    num[tot]++;
    sum[tot] += a[x];
    vis[x] = false;

}
void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    s.push(x);
    vis[x] = true;
    for (auto to : e[x]){
        if(!dfn[to]){
            tarjan(to);
            low[x] = min(low[x], low[to]);
        }
        else if(vis[to])
            low[x] = min(low[x], dfn[to]);
    }
    if(low[x] == dfn[x]){
        ++tot;
        while(s.top() != x){
            dos(s.top());
        }
      dos(s.top());
    }
}

比如这个代码的话,在访问结束cpp low[x] == dfn[x] 为何要更新vis[x]为0呢,连成强联通分量之后不应该不会访问这个点了吗?

不解,求大神救救

2023/10/31 19:51
加载中...