做了一道需要求割边的题
写成这样就 A 了
void Tarjan(int u, int from) {
low[u] = dfn[u] = ++tot;
for (int i = h[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
Tarjan(v, i ^ 1);
if (low[v] > dfn[u])
bridge[i] = bridge[i ^ 1] = true;
low[u] = min(low[u], low[v]);
} else if (i != from) low[u] = min(low[u], dfn[v]);
}
}
写成这样就 WA 了
void Tarjan(int u, int from) {
low[u] = dfn[u] = ++tot;
for (int i = h[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
Tarjan(v, i);
if (low[v] > dfn[u])
bridge[i] = bridge[i ^ 1] = true;
low[u] = min(low[u], low[v]);
} else if (i != from ^ 1) low[u] = min(low[u], dfn[v]);
}
}
不太明白为什么,以前都是按照第 2 种写的,貌似没有什么问题,哪位巨佬能帮忙解答一下?