Content #
若x不是根节点，则x是割点，当且仅当在搜索树上存在x的一个子节点y，满足low[y]≥dfn[x]；若x是根节点，则x是割点，当且仅当在搜索树上至少存在两个子节点，满足该条件。也就是说，如果不是根，且孩子的low值大于或等于自己的dfn值，则该节点就是割点；如果是根，则至少需要两个孩子满足条件。
void find_cut_point(int u, int father) {
dfn[u] = low[u] = num++;
int count = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == father) continue;
if (!dfn[v]) {
find_cut_point(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
count++;
if (u != root || count > 1) {
cout << "u is cut point." << endl;
}
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
From #
《算法训练营入门篇》 陈小玉