about tarjan割点
  • 板块灌水区
  • 楼主Archy_
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/8/21 10:40
  • 上次更新2024/8/21 13:07:15
查看原帖
about tarjan割点
895312
Archy_楼主2024/8/21 10:40

在做tarjan的时候那个根节点不是要看它的儿子是不是大于等于 2,如果是那么一定是割点。

void tarjan(int x) {
	dfn[x] = low[x] = ++ dfncnt;
	int child = 0;
	for (auto y : g[x]) {
		if (!dfn[y]) {
			tarjan(y), low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x] && x != root) cut[x] = true;
			if (x == root) child ++;
		} else low[x] = min(low[x], dfn[y]);
	}
	if (child >= 2 && x == root) cut[x] = true;
}

但是我做的题,以及之前看题解的时候发现,这个特判似乎不用加?这是为什么,是题目的性质还是我记错了?那个割点模板就必须加这个特判。

2024/8/21 10:40
加载中...