社区讨论

关于tarjan

P3387【模板】缩点参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mhjig72d
此快照首次捕获于
2025/11/04 03:05
4 个月前
此快照最后确认于
2025/11/04 03:05
4 个月前
查看原帖
这是我的tarjan函数
CPP
void 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(); 
	}
}
当遍历下一个节点已经在栈里时,我写的是
CPP
low[x] = min(low[x], low[V[x][i]]);
而我发现,改成
CPP
low[x] = min(low[x], dfn[V[x][i]]);
也对
这俩都行的原理大概能想明白,但希望有大佬能解释更清楚,另外在某种特定条件下这里其中一个会不会失效?

回复

7 条回复,欢迎继续交流。

正在加载回复...