连通性相关

Tangninghaha · 2025-01-10 07:52:58 · 算法·理论

强连通分量 / SCC

定义

强连通：有向图中，如果两个点能互相到达，称这两个点强连通。

强连通分量：一个极大的强连通子图。

一个有向图中，一个点属于一个强连通分量。反证：假设一个点属于两个强连通分量，那么这两个强连通分量可以合并为同一个。

求解

使用 Tarjan 算法，定义 low 和 dfn，建立出 DFS 生成树，使用栈辅助求解：

• 初始化 low 和 dfn，使其等于 x 的 dfn 序
  • 枚举 x 的出边，假设其连接 y
  • 若 y 已经遍历过
    • 若 y 不在栈中，则跳过
    • 若 y 在栈中，那么用 dfn[y] 更新 low[x]
  • 若 y 未遍历过
    • 遍历 y，用 low[y] 更新 low[x]
  • 若 low[x] 不超过 dfn[x]，说明栈中 x 直到栈顶的节点构成了一个强连通分量。

由于使用了栈，得到的 SCC 标号是逆拓扑序。

应用

常用于将一些有向有环图进行缩 SCC 的操作，将其变为一个 DAG（有向无环图）以便于进行处理。

割点和桥

定义

割点定义为无向图中，删去这个点之后能使图不连通的点。

桥（或割边）定义为无向图中，删去这条边之后能使图不连通的边。

求解

仍然使用 Tarjan 算法，类似地，定义 low 和 dfn，建立出 DFS 生成树：

• 初始化 low 和 dfn，使其等于 x 的 dfn 序

  • 枚举 x 的出边，假设其连接 y

  • 若 y 已经遍历过，用 dfn[y] 更新 low[x]

  • 若 y 未遍历过，则遍历 y，用 low[y] 更新 low[x]

  • 若 low[x] 不超过 dfn[fa]，则 fa 为一个割点。

这个流程在 DFS 生成树的根不适用，需要特殊判断根的儿子数量（注意不是连边数量），若大于 1 则根是割点。

桥的求解类似，只要将判断条件 low[x]<=dfn[fa] 改为 low[x]<dfn[fa]，则边 (x，fa) 是一条割边。

注意如果有重边，则可能出现两条到父亲的边，需要记录从哪一条边来，另一条边可以更新 low。

割点代码：

const int N = 2e4 + 5, M = 2e5 + 5;
struct Graph {
    int head[N], nxt[M], to[M], tot;
    void add(int u, int v) {
        nxt[++tot] = head[u];
        to[tot] = v;
        head[u] = tot;
    }
} G;
int dfn[N], low[N], dfn_cnt, rt_cnt;
bool is_cut[N];

void dfs(int x, int fa) {
    low[x] = dfn[x] = ++dfn_cnt;
    for (int i = G.head[x]; i; i = G.nxt[i]) {
        if (G.to[i] == fa) continue;
        if (dfn[G.to[i]]) {
            low[x] = min(low[x], dfn[G.to[i]]);
            continue;
        }
        if (!fa) ++rt_cnt;
        dfs(G.to[i], x);
        low[x] = min(low[x], low[G.to[i]]);
    }
    if (low[x] >= dfn[x]) {
        is_cut[fa] = true;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        G.add(u, v);
        G.add(v, u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            rt_cnt = 0;
            dfs(i, 0);
            is_cut[i] = (rt_cnt > 1);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) cnt += is_cut[i];
    cout << cnt << '\n';
    for (int i = 1; i <= n; ++i) {
        if (is_cut[i]) {
            cout << i << ' ';
        }
    }
    return 0;
}

双连通分量

定义

边双连通：在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通。

点双连通：在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。

极大的边双连通子图称为边双连通分量，极大的点双连通子图称为点双连通分量。

边双连通分量

每一个点属于至多一个边双。

求解边双连通分量和强连通分量是几乎相同的，唯一区别是边是双向的，要记录来时的边（注意不是点，因为可能会有重边）不走，并且没有横叉边的情况，所以不用记录是否在栈中（返祖边必定在栈中）。

const int N = 5e5 + 5, M = 4e6 + 5;
struct Graph {
    int head[N], nxt[M], to[M], tot;
    Graph() { tot = 1; }
    void add(int u, int v) {
        nxt[++tot] = head[u];
        to[tot] = v;
        head[u] = tot;
    }
} G;

int rt;
int dfn[N], dfn_cnt, low[N];
int sta[N], top;
vector<vector<int>> ans;
void dfs(int x, int from) {
    dfn[x] = low[x] = ++dfn_cnt;
    sta[++top] = x;
    for (int i = G.head[x]; i; i = G.nxt[i]) {
        if ((i ^ 1) == from) continue;
        if (dfn[G.to[i]]) {
            low[x] = min(low[x], dfn[G.to[i]]);
            continue;
        }
        dfs(G.to[i], i);
        low[x] = min(low[x], low[G.to[i]]);
    }
    if (low[x] == dfn[x]) {
        ans.push_back(vector<int>());
        while (sta[top + 1] != x) {
            ans.back().push_back(sta[top--]);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        G.add(u, v);
        G.add(v, u);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) rt = i, dfs(i, 0);
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i.size() << ' ';
        for (auto j : i)
            cout << j << ' ';
        cout << '\n';
    }
}

点双连通分量

有性质：

1. 两个点双至多有一个公共点，并且公共点是割点，否则可以导出这两个点双可以合并。
2. 一个点双中，dfn 序最小的是割点或树根。

考虑一个非根节点，若这个点是割点，那么它与到栈顶的节点形成了一个点双。

考虑一个根节点，若这个点是孤立点，则它是一个点双。否则它到栈顶的点也形成一个点双。

注意最后割点不能出栈，因为可能还有其余的点双包括这个点。

const int N = 5e5 + 5, M = 4e6 + 5;

struct Graph {
    int head[N], nxt[M], to[M], tot;
    Graph() { tot = 1; }
    void add(int u, int v) {
        nxt[++tot] = head[u];
        to[tot] = v;
        head[u] = tot;
    }
} G;

int rt;
int dfn[N], low[N], dfn_cnt, sta[N], top;
vector<vector<int>> ans;
void dfs(int x, int from) {
    dfn[x] = low[x] = ++dfn_cnt;
    if (x == rt && !G.head[x]) {
        ans.push_back(vector<int>(1, x));
        return;
    }
    sta[++top] = x;
    for (int i = G.head[x]; i; i = G.nxt[i]) {
        if ((i ^ 1) == from) continue;
        if (dfn[G.to[i]]) {
            low[x] = min(low[x], dfn[G.to[i]]);
            continue;
        }
        dfs(G.to[i], i);
        low[x] = min(low[x], low[G.to[i]]);
        if (low[G.to[i]] >= dfn[x]) {
            ans.push_back(vector<int>());
            while (sta[top + 1] != G.to[i]) {
                ans.back().push_back(sta[top--]);
            }
            ans.back().push_back(x);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        if (u == v) continue;
        G.add(u, v);
        G.add(v, u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) rt = i, dfs(i, 0);
    }
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i.size() << ' ';
        for (auto j : i)
            cout << j << ' ';
        cout << '\n';
    }
}