有关 Tarjan 有向图求强连通分量的一个小问题
  • 板块学术版
  • 楼主brealid
  • 当前回复12
  • 已保存回复12
  • 发布时间2020/6/15 21:30
  • 上次更新2023/11/7 00:34:32
查看原帖
有关 Tarjan 有向图求强连通分量的一个小问题
63720
brealid楼主2020/6/15 21:30

今天在写 Tarjan 有向图求强连通分量时,一下子没想起“弹栈”那一段怎么写,于是 yy 出一种写法

if (dfn[u] == low[u]) {
    while (low[s[top]] >= low[u]) {
        inStack[s[top]] = false;
        kind[s[top--]] = kindsCnt;
        kindCnt[kindsCnt]++;
    }
}

这是能够过的
后来一看发现,正确的写法应该是这样的

if (dfn[u] == low[u]) {
    kindsCnt++;
    do {
        inStack[s[top]] = false;
        kind[s[top--]] = kindsCnt;
        kindCnt[kindsCnt]++;
    } while (s[top] != u);
}

while 循环的终止条件不同。

我已经查过 Baidu 了,但是没查到有关第一种写法的内容,主流写法都是第二种

我想问一下,这种写法是否正确?
(如果不是,麻烦提供 Hack 数据)
感激不尽。

2020/6/15 21:30
加载中...