关于tarjan求强连通分量中的in_stack
  • 板块学术版
  • 楼主ZnPdCo
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/2/27 20:50
  • 上次更新2024/2/27 20:53:30
查看原帖
关于tarjan求强连通分量中的in_stack
560700
ZnPdCo楼主2024/2/27 20:50

在网上的某个博客中的代码如下:

其中博主直接使用 co 来判断是否在栈中。而 oi-wiki 上的代码:

int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

则使用了 in_stack 并且会在退栈之后归零。

以上两种方法都经常使用而且经受了多题的打压都没出错,请问两种做法是都正确的,还是博客的做法是错误的?如果错误了,能否给出hack或构造方法?

2024/2/27 20:50
加载中...