关于Tarjan求割边的一些问题
查看原帖
关于Tarjan求割边的一些问题
464528
见贤思齐_Seakies楼主2023/6/23 18:28

做了一道需要求割边的题

写成这样就 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 种写的,貌似没有什么问题,哪位巨佬能帮忙解答一下?

2023/6/23 18:28
加载中...