今天在写 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 数据)
感激不尽。