社区讨论
关于tarjan
P3387【模板】缩点参与者 5已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mhjig72d
- 此快照首次捕获于
- 2025/11/04 03:05 4 个月前
- 此快照最后确认于
- 2025/11/04 03:05 4 个月前
这是我的tarjan函数
CPPvoid tarjan(ll x) {
dfncnt++;
dfn[x] = dfncnt;
low[x] = dfn[x];
S.push(x);
book[x] = 1;
for (int i = 0; i < V[x].size(); i++) {
if (!dfn[V[x][i]]) {
tarjan(V[x][i]);
low[x] = min(low[x], low[V[x][i]]);
} else if (book[V[x][i]]) {
low[x] = min(low[x], low[V[x][i]]);
}
}
if (low[x] == dfn[x]) {
sccnt++;
while (S.top() != x) {
book[S.top()] = 0;
blt[S.top()] = sccnt;
S.pop();
}
book[S.top()] = 0;
blt[S.top()] = sccnt;
S.pop();
}
}
当遍历下一个节点已经在栈里时,我写的是
CPPlow[x] = min(low[x], low[V[x][i]]);
而我发现,改成
CPPlow[x] = min(low[x], dfn[V[x][i]]);
也对
这俩都行的原理大概能想明白,但希望有大佬能解释更清楚,另外在某种特定条件下这里其中一个会不会失效?
回复
共 7 条回复,欢迎继续交流。
正在加载回复...