关于一些图论连通性的算法总结

ShiRoZeTsu · 2023-10-17 21:01:00 · 个人记录

本文总结了一些图论连通性相关的板子，用来复习。以下是清单：

• 强连通分量、边双连通分量、点双连通分量的缩点；

• 割点、割边；

• 圆方树。

强连通分量缩点

模板：P3387 【模板】缩点

思路：

• dfs。在一条边 (u, v) 中，若 v 还未被遍历（无 dfn），则先 dfs 点 v，再更新 u 的 low 值；否则，若 v 在栈中，也更新 u 的 low 值。

• 跑完边后，若 u = low(u)，则找到一个强连通分量（单点也算）。循环取出栈顶的点，标记 scc，统计贡献，直到取出点 u 自己停止。

核心代码：

void getscc(int u) {
    low[u] = dfn[u] = ++dfncnt;
    stk[++top] = u;
    vis[u] = true;
    for(int i = HEAD[u]; i; i = E[i].nxt) {
        int v = E[i].to;
        if(!dfn[v]) {
            getscc(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], low[v]);
    }
    if(dfn[u] == low[u]) {
        int v;
        while((v = stk[top--])) {
            scc[v] = u;
            vis[v] = false;
            if(u == v) break;
            w[u] += w[v];
        }
    }
}

全部代码（无注释）与全部代码（有注释）

边双连通分量缩点

模板：P8436 【模板】边双连通分量

思路：与强连通分量缩点极其相似，唯一不同的就是需要判断这条边是不是刚刚走过。如果已经走过，就不能再走了。判断边的方式可以通过链式前向星编号的奇偶性。

核心代码：

void getecc(int u, int last) {
    low[u] = dfn[u] = ++dfncnt;
    stk[++top] = u;
    vis[u] = true;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(i == last) continue;
        if(!dfn[v]) {
            getecc(v, i^1);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], low[v]);
    }
    vis[u] = false;
    if(dfn[u] == low[u]) {
        ans.push_back(u);
        int v;
        while((v = stk[top--])) {
            ecc[u].push_back(v);
            if(u == v) break;
        }
    }
}

全部代码

点双连通分量缩点

模板：P8435 【模板】点双连通分量

思路：

• 与前两种有很大的不同，由于每个点可能属于多个点双，所以不能使用 vis 来记录元素是否在栈中，而要一边跑边，一边找点双；

• 具体方法是，对于一条边 (u, v)，若有 low(v) \geq dfn(u)，则说明存在一个点双；

• 将 u 加入 v 的点双，同时不断将栈顶元素弹出，加入 v 的点双，直到栈顶元素为 v。

核心代码：

void getvcc(int u, int last) {
    low[u] = dfn[u] = ++dfncnt;
    stk[++top] = u;
    int son = 0;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(i == last) continue;
        if(!dfn[v]) {
            son++;
            getvcc(v, i^1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                int x;
                ans.push_back(v);
                vcc[v].push_back(u);
                while((x = stk[top--])) {
                    vcc[v].push_back(x);
                    if(x == v) break;
                }
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if(!last && !son) {
        ans.push_back(u);
        vcc[u].push_back(u);
    }
}

全部代码

割点

模板：P3388 【模板】割点（割顶）

思路：

• 假如从点 r 开始 dfs，如果 dfs 了两个它的相邻的点，则证明点 r 是一个割点；

• 由于不需要缩点，所以不用开栈；

• 对于一条边 (u, v)，若 low(v) \geq dfn(u)，则证明 u 是一个割点（u \neq r）。

核心代码：

void getcut(int u, int r) {
    low[u] = dfn[u] = ++dfncnt;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(!dfn[v]) {
            getcut(v, r);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u] && u != r) cut[u] = true;
            if(u == r) son++;
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if(u == r && son >= 2) cut[u] = true;
}

全部代码

割边

思路：求完边双之后，对于每一条边 (u, v)，若 ecc(u) \neq ecc(v)，则这是一条割边。

圆方树

定义：将原图的每个点称作圆点，将每个点双称作方点，每个圆点向它所属的点双连边，可以形成一个树形结构。这个树形结构就叫圆方树。

思路：

• 在求点双时顺便连边；

• 由于 dfs 自带深度关系，可以直接建边。

核心代码：

void build(int u, int last) {
    low[u] = dfn[u] = ++dfncnt;
    stk[++top] = u;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(i == last) continue;
        if(!dfn[v]) {
            build(v, i^1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                vcccnt++;
                addedge(u, n+vcccnt);
                int x;
                while((x = stk[top--])) {
                    addedge(n+vcccnt, x);
                    if(x == v) break;
                }
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

感谢阅读！有内容或欠缺还会再补充！