强连通分量

2023-02-12 | 阅读：次

===

Index

有向图强连通分量
无向图的双连通分量

有向图强连通分量

强连通：若一张有向图的节点两两互相可达，则称这张图是强连通的。强连通分量(SCC)：极大的强连通子图

scc模板

使用数组

时间戳 dfn[x]: 节点x第一次被访问的顺序。
追溯值 low[x]: 从节点x出发，所能访问到的最早时间戳。

struct SCC {
    int n, cnt = 0;
    vector<pair<int, int>> edges;
    vector<int> low, dfn, ids, in, out;
    explicit SCC(int n) : n(n), low(n), dfn(n, -1), ids(n){}
    void add_edge(int from, int to) { edges.push_back({from, to}); }

    void scc_ids() {
        vector<int> start(n + 1), elist(edges.size()), visited;
        for (auto &e : edges) 
            start[e.first + 1]++;
        for (int i = 1; i <= n; ++i) 
            start[i] += start[i - 1];
        auto counter = start;
        for (auto &e : edges)
            elist[counter[e.first]++] = e.second;
        int now_dfn = 0;
        visited.reserve(n);
        auto dfs = [&](auto self, int v) -> void {
            low[v] = dfn[v] = now_dfn++;
            visited.push_back(v);
            for (int i = start[v]; i < start[v + 1]; i++) {
                auto to = elist[i];
                if (dfn[to] == -1) {
                    self(self, to);
                    low[v] = min(low[v], low[to]);
                } else {
                    low[v] = min(low[v], dfn[to]);
                }
            }
            if (low[v] == dfn[v]) {
                while (true) {
                    int u = visited.back();
                    visited.pop_back();
                    dfn[u] = n, ids[u] = cnt;
                    if (u == v) break;
                }
                cnt++;
            }
        };
        for (int i = 0; i < n; i++) if (dfn[i] == -1) dfs(dfs, i);
        in.assign(cnt, 0);
        for (auto& x : ids) {
            x = cnt - 1 - x;
            in[x]++;
        }
    }

    vector<vector<int>> scc(bool cal_degree = false) {
        scc_ids();
        vector<vector<int>> groups(cnt);
        for (int i = 0; i < cnt; ++i) groups[i].reserve(in[i]);
        for (int i = 0; i < n; i++) groups[ids[i]].push_back(i);
        if (cal_degree) {
            in.assign(cnt, 0), out.assign(cnt, 0);
            for (auto &[from, to]: edges) {
                int x = ids[from], y = ids[to];
                if (x != y) in[y]++, out[x]++;
            }
        }
        return groups;
    }
};

使用说明

初始化, 时间复杂度 O(n)

SCC g(n);

添加一条有向边, 均摊复杂度 O(1)

g.add_edge(from, to);

求强连通分量时间复杂度 O(n + m)

vector<vector<int>> ans = g.scc();

返回一个二维 vector, 满足

每个顶点恰好出现在一个顶点数组中
每个数组中的顶点对应于图中的一个强连通分量
顶点数组按照拓扑序排序，例如，节点 (u, v) 是两个不同强连通分量中的节点，如果有一条从u到v的直接有向边，则包含u的节点数组排在包含v的节点数组前面。

有向图强连通分量个数

int m = g.cnt;

缩点后的拓扑图每个强连通分量表示的新点的入度和出度

其中 in[i]表示缩点后的拓扑图第i个强连通分量的入度，out[i]表示出度。

vector<int> in(cnt), out(cnt);

有向图中能被所有节点到达的节点数目

luogu p2341

给一个有向图，求图中有多少个节点满足：从其它任意节点出发，均有至少一条路径到达该节点。

1 <= n <= 1e4
1 <= m <= 5e4

分析

使用scc缩点，在缩点后的有向拓扑图中，如果有大雨等于两个出度为0的点，则答案为0，因为这两个点表示的强连通分量一定互相不可达，否则为出度为0的点表示的强连通分量重的节点数目。

// scc模板

int main() {
    int n, m;
    cin >> n >> m;
    SCC g(n);
    for(int i = 0, u, v; i < m; ++i) {
       cin >> u >> v;
       u--,v--;
       g.add_edge(u, v);
    }
    auto a = g.scc();
    int p = 0, q = 0;
    for (int i = 0; i < g.cnt; ++i) {
        if (g.out[i] == 0) p++, q += a[i].size();
    }
    cout << (p > 1 ? 0 : q) << "\n";
    return 0;
}

有向图变为强连通图需要添加的边数

luogu p2812

给定一个有向图，求

至少选择多少节点作为网络源点，能使所有节点均有网络可达。
至少需要添加多少条边，能让有向图变为强连通图。

1 <= n <= 1e4
1 <= m <= 5e4

分析

答案为缩点后入度为0的点的数目
答案为缩点后入度为0和出度为0数量的最大值。如果只有一个强连通分量，则答案为0.

// scc模板
int main() {
    int n;
    cin >> n;
    SCC g(n);
    for(int i = 0; i < n; ++i) {
        int x;
        while (cin >> x && x != 0) {
            x--;
            g.add_edge(i, x);
        }
    }
    auto a = g.scc();
    int p = 0, q = 0;
    for (int i = 0; i < g.cnt; ++i) {
        p += (g.in[i] == 0);
        q += (g.out[i] == 0);
    }
    cout << p << "\n" << (g.cnt == 1 ? 0 : max(p, q)) << "\n";
    return 0;
}

无向图的双连通分量

边双连通分量

桥(割边)

对于一个无向图，如果删掉一条边后，连通块个数增加了，则称这条边为桥或割边。

极大的不含有桥的连通子图成为边双连通分量。

割边判定

当搜索树上存在x的一个子节点y，满足 low[y]>dfn[x] 则(x,y)这条边就是桥。

性质

在边的双连通分量中，任意两个节点都包含两条不相交的路径(边不相交)
将边双连通分量缩为一个点，缩完点后得到的图一定是一棵树(或森林)，树边就是原来的割边。

数组和变量

n 顶点数，m 为边数，dcc_cnt为边的双连通分量数目
ids: 存每个顶点所在的边双连通分量编号
deg, 边双连通分量缩点后，每个连通分量的度数
is_bridge 存储某条边是否是桥

模板

struct Edcc {
    int n, m = 0, dcc_cnt = 0, init = 0;
    vector<vector<pair<int,int>>> g;
    vector<array<int, 2>> elist;
    vector<int> dfn, low, ids, deg;
    vector<bool> is_bridge;

    Edcc(int n = 0): n(n), dfn(n, -1), low(n), g(n), ids(n){}

    void add_edge(int a, int b) {
        g[a].emplace_back(b, m);
        g[b].emplace_back(a, m);
        elist.push_back({a, b});
        m++;
    }

    void get_ids() {
        init = 1;
        vector<bool> visited(n, false);
        is_bridge.assign(m, false);
        vector<int> stk;
        int now_dfn = 0;

        function<void(int, int)> dfs = [&](int u, int fa) {
            visited[u] = true;
            stk.push_back(u);
            low[u] = dfn[u] = now_dfn++;
            int pa_cnt = 0;
            for (auto &[v, id]: g[u]) {
                if (v == fa && pa_cnt++ == 0) continue;
                if (visited[v]) {
                    low[u] = min(low[u], dfn[v]);
                } else {
                    dfs(v, u);
                    is_bridge[id] = low[v] > dfn[u];
                    low[u] = min(low[u], low[v]);
                }
            }
            if (dfn[u] == low[u]) {
                while (true) {
                    int v = stk.back();
                    stk.pop_back();
                    ids[v] = dcc_cnt;
                    if (u == v) break;
                }
                dcc_cnt ++;
            }
        };
        
        for (int i = 0; i < n; i++)
            if (!~dfn[i])
                dfs(i, -1);
    }

    vector<vector<int>> edcc() {
        if (!init) get_ids();
        vector<vector<int>> groups(dcc_cnt);
        for (int i = 0; i < n; ++i) {
            groups[ids[i]].push_back(i);
        }
        deg.assign(dcc_cnt, 0);
        for (int i = 0; i < m; ++i) {
            if (is_bridge[i]) {
                deg[ids[elist[i][0]]]++;
                deg[ids[elist[i][1]]]++;
            }
        }
        return groups;
    }

    vector<vector<int>> bridge_tree() {
        if (!init) get_ids();
        vector<vector<int>> tr(dcc_cnt);
        for (int i = 0; i < m; ++i) {
            if (is_bridge[i]) {
                int x = ids[elist[i][0]], y = ids[elist[i][1]];
                tr[x].push_back(y);
                tr[y].push_back(x);
            }
        }
        return tr;
    }
};

使用方法

初始化时间复杂度 O(n)

Edcc g(n);

添加一条边，时间复杂度 O(1)

g.add_edge(u, v);

求边的双连通分量

时间复杂度 O(n + m)

返回一个二维vector, dcc[i]里存的是连通分量id为i的顶点编号。

auto dcc = g.edcc();

每个顶点所在连通分量编号

for (int i = 0; i < n; ++i) {
    cout << g.ids[i] << " \n"[i == n - 1];
}

判断某条边是否是桥

for (int i = 0; i < m; ++i) {
    cout << g.is_bridge[i] << " \n"[i == n - 1];
}

边的双连通分量缩点后形成的树

时间复杂度 O(n + m)

auto t = g.bridge_tree();

无向连通图最少加几条边能变为一个边双连通分量

acw 395冗余路径

给定一个无向连通图，求最少加多少条边，使任意两点之间至少有两条相互分离的路径。

1 <= n <= 5000
n - 1 <= m <= 10000

分析

结论：任意两点之间至少有两条相互分离的路径等价于整个图为边双连通分量。假设边双连通分量缩点后度为1的节点个数为cnt, 需要加的边数等于(cnt+1)/2

int main() {
    int n, m;
    cin >> n >> m;
    Edcc g(n);
    vector<vector<int>> E(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        u--, v--;
        E[u].push_back(v);
        E[v].push_back(u);
        g.add_edge(u, v);
    }
    g.edcc();
    int cnt = 0;
    for (int x : g.deg) {
        if (x == 1) cnt++;
    }
    cout << (cnt + 1) / 2 << "\n";
    return 0;
}

点双连通分量

割点

对于一个无向图，如果把一个点删除后，连通块个数增加了，则称这个点为割点

极大的不含有割点的连通子图成为点双连通分量。

割点判定

当x 不是搜索树的根节点： x是割点当且仅当搜索树存在一子节点y，满足 dfn[x] <= low[y].
当x 是根节点： x 是割点当且仅当搜索树存在两个子节点y1，y2 满足上式.

模板

struct Vdcc {
    int n, m = 0, init = 0;
    vector<vector<pair<int,int>>> g;
    vector<array<int, 2>> elist;
    vector<int> dfn, low, stack;
    vector<bool>  is_cut, is_bridge;
    vector<vector<int>> components;

    Vdcc(int n) : n(n), g(n), dfn(n), low(n){}

    void add_edge(int a, int b) {
        g[a].emplace_back(b, m);
        g[b].emplace_back(a, m);
        elist.push_back({a, b});
        m++;
    }

    void build(int root = -1) {
        init = 1;
        vector<bool> visited(n, false);
        is_cut.assign(n, false);
        is_bridge.assign(m, false);
        int now_dfn = 0;

        function<void(int, int)> dfs = [&](int u, int fa) {
            visited[u] = true;
            low[u] =  dfn[u] = now_dfn++;
            is_cut[u] = false;
            int pa_cnt = 0, child = 0;
            for (auto &[v, id] : g[u]) {
                if (v == fa && pa_cnt++ == 0) continue;
                if (visited[v]) {
                    low[u] = min(low[u], dfn[v]);
                    if (dfn[v] < dfn[u]) stack.push_back(u);
                } else {
                    int size = int(stack.size());
                    dfs(v, u);
                    child++;
                    low[u] = min(low[u], low[v]);
                    if (low[v] > dfn[u]) {
                        is_bridge[id] = true;
                        vector<int> comp = {u, v};
                        if (comp[0] > comp[1]) swap(comp[0], comp[1]);
                        components.push_back(comp);
                    } else if (low[v] == dfn[u]) {
                        stack.push_back(u);
                        vector<int> comp(stack.begin() + size, stack.end());
                        sort(comp.begin(), comp.end());
                        comp.erase(unique(comp.begin(), comp.end()), comp.end());
                        components.push_back(comp);
                        stack.resize(size);
                    } else {
                        stack.push_back(u);
                    }
                    if (low[v] >= dfn[u]) is_cut[u] = true;
                }
            }
            if (fa < 0) is_cut[u] = child > 1;
        };

        if (0 <= root && root < n)
            dfs(root, -1);
        for (int i = 0; i < n; i++)
            if (!visited[i])
                dfs(i, -1);
    }
    
};

// Note: instead of a block-cut tree this is technically a block-vertex tree, which ends up being much easier to use.
struct block_cut_tree {
    Vdcc &bi_comps;

    int n, BC, T;
    vector<vector<int>> g;
    vector<int> fa, dep;

    block_cut_tree(Vdcc &_bi_comps) : bi_comps(_bi_comps) {}

    void build() {
        n = bi_comps.n, BC = int(bi_comps.components.size());
        T = n + BC;
        g.assign(T, {});

        auto add_edge = [&](int a, int b) {
            assert((a < n) ^ (b < n));
            g[a].push_back(b);
            g[b].push_back(a);
        };

        function<void(int, int)> dfs = [&](int u, int pa) {
            fa[u] = pa, dep[u] = pa < 0 ? 0 : dep[pa] + 1;
            for (int v : g[u]) if (v != pa)
                dfs(v, u);
        };

        for (int bc = 0; bc < BC; bc++)
            for (int x : bi_comps.components[bc])
                add_edge(x, n + bc);

        fa.assign(T, -1);
        dep.resize(T);

        for (int root = 0; root < T; root++)
            if (fa[root] < 0)
                dfs(root, -1);
    }

    bool same_component(int a, int b) const {
        if (dep[a] > dep[b])
            swap(a, b);
        return a == b || (dep[b] == dep[a] + 2 && fa[fa[b]] == a) || (fa[a] >= 0 && fa[a] == fa[b]);
    }
};