关于无向图缩点的疑问
  • 板块学术版
  • 楼主too_simple
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/2/23 18:36
  • 上次更新2023/10/24 00:01:38
查看原帖
关于无向图缩点的疑问
366937
too_simple楼主2023/2/23 18:36
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cnt;
    ins[u] = 1, stk[++top] = u;
    for (int i = head[u], v; i; i = e[i].nxt) {
        v = e[i].to;
        if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        } else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        p++;
        int x;
        do {
            // 因为不需要知道每个边双连通分量里都有哪些点,只记录每个点属于哪个边双连通分量即可。
            x = stk[top--];
            ins[x] = 0;
            bel[x] = p;
            V[p]++; // 累加该边双连通分量内点数
        } while (x != u);
    }
}

上面本来是有向图的缩点,但加上下面这行代码就能过无向图的缩点:

if (v == fa) continue;
2023/2/23 18:36
加载中...