桥与边双联通分量

板子和常识

https://oi-wiki.org/graph/bcc/

板子用的是 tarjan算法2 的思想

只能跑无向图

  • 理论基础

    • SCC部分

      对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 (u) 使得 $\texttt{dfn}_u=\texttt{low}_u $。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 (dfn) 和 (low) 值最小，不会被该连通分量中的其他结点所影响。

      因此，在回溯的过程中，判定 $\texttt{dfn}_u=\texttt{low}_u $ 是否成立，如果成立，则栈中 (u) 及其上方的结点构成一个 SCC。

    • 桥与边双联通部分

      我们先总结出一个重要的性质，在无向图中，DFS 生成树上的边不是树边就只有非树边。

      我们联系一下求强连通分量的方法，在无向图中只要一个分量没有桥，那么在 DFS 生成树上，它的所有点都在同一个强连通分量中。

      反过来，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量。

      可以发现，求边双连通分量的过程实际上就是求强连通分量的过程

  • 板子解释

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    class EdgeBC {
        const std::vector<std::vector<int>> &e;//存原来的无向图
        std::vector<int> stk; // stack
        int r = 0, cur = 0;

        void dfs(int x, int fa) {//dfs生成树上跑强连通分量
            dfn[x] = low[x] = cur++;
            stk[++r] = x;//把本次递归到的所有节点（也就是该联通快所有节点）压栈

            for (int y : e[x]) {
                if (y == fa) {//如果邻接节点 y 是当前节点的父节点，则跳过（将 fa 反转的目的是为了避免将父节点自身当作回边处理）。
                    fa = ~fa;
                    continue;
                }
              //强连通分量
                if (dfn[y] == -1) {
                    dfs(y, x);
                    low[x] = std::min(low[x], low[y]);
                } else {
                    low[x] = std::min(low[x], dfn[y]);
                }
            }
    				
            if (dfn[x] == low[x]) {//符合强连通分量条件
                int y;
                do {
                    y = stk[r--];
                    bel[y] = cntBlock;//bel[y](y结点对应的联通快编号)
                } while (y != x);
                cntBlock += 1;
            }
        }

    public:
        // original graph
        std::vector<int> dfn, low, bel, cutDeg;//bel[y](y结点对应的联通快编号)
        // shrinking graph
        std::vector<std::vector<int>> g;//由桥构成的无根树
        int cntBlock = 0, componentNum = 0;

        EdgeBC(const std::vector<std::vector<int>> &e)
            : e(e), dfn(e.size(), -1), low(e.size()), bel(e.size(), -1), cutDeg(e.size()) {
            int n = e.size();
            q.assign(n + 1, 0);

            for (int i = 0; i < n; i++) {
                if (dfn[i] == -1) {
                    componentNum += 1;
                    dfs(i, -1);
                }
            }

            g.resize(cntBlock);
            for (int x = 0; x < n; x++) {
                for (int y : e[x]) {
                    if (bel[x] == bel[y])
                        continue;
                    g[bel[x]].push_back(bel[y]);
                }
            }
        }
    };

怎么用

  • 求每个边双联通分量

https://www.luogu.com.cn/problem/P8436

由理论基础中：

反过来，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量。

显然，强连通分量就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class EdgeBC {
    const std::vector<std::vector<int>> &e;
    std::vector<int> q; // stack
    int r = 0, cur = 0;

    void dfs(int x, int fa) {
        dfn[x] = low[x] = cur++;
        q[++r] = x;

        for (int y : e[x]) {
            if (y == fa) {
                fa = ~fa;
                continue;
            }
            if (dfn[y] == -1) {
                dfs(y, x);
                low[x] = std::min(low[x], low[y]);
            } else {
                low[x] = std::min(low[x], dfn[y]);
            }
        }

        if (dfn[x] == low[x]) {
            int y;
            std::vector<int> res{x};
            do {
                y = q[r--];
                bel[y] = cntBlock; 
                if (y != x) res.push_back(y);//把每个强连通分量统计进去就行
            } while (y != x);
            resEdgeBC.push_back(res);
            cntBlock += 1;
        }
    }

public:
    // original graph
    std::vector<int> dfn, low, bel, cutDeg;
    std::vector<std::vector<int>> resEdgeBC;

    // shrinking graph
    std::vector<std::vector<int>> g;//就是由割边组成的无根树
    //g.size() - 1就是割边数量
    int cntBlock = 0, componentNum = 0;

    EdgeBC(const std::vector<std::vector<int>> &e)
        : e(e), dfn(e.size(), -1), low(e.size()), bel(e.size(), -1), cutDeg(e.size()) {
        int n = e.size();
        q.assign(n + 1, 0);

        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                componentNum += 1;
                dfs(i, -1);
            }
        }

        g.resize(cntBlock);
        for (int x = 0; x < n; x++) {
            for (int y : e[x]) {
                if (bel[x] == bel[y])
                    continue;
                g[bel[x]].push_back(bel[y]);
            }
        }
    }
};

void solve()
{
    int n, m; std::cin >> n >> m;
    std::vector adj(n, std::vector<int>()); for (int i = 0, u, v; i < m; i++) {std::cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u);}
    auto res{EdgeBC(adj).resEdgeBC};
    std::cout << std::size(res) << '\n';
    for (auto& g : res) {
        std::cout << std::size(g) << ' '; for (auto& x : g) {std::cout << x + 1 << ' ';} std::cout << "\n";
    }

}

由桥的定义：

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

那么对于一条边，如果两个顶点不属于同一个联通快，那显然就是一个桥。

对于该板子的使用，即对于 bel[x] != bel[y]，((x, y), (y, x)) 都是桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class EdgeBC {
    const std::vector<std::vector<int>> &e;
    std::vector<int> q; // stack
    int r = 0, cur = 0;

    void dfs(int x, int fa) {
        dfn[x] = low[x] = cur++;
        q[++r] = x;

        for (int y : e[x]) {
            if (y == fa) {
                fa = ~fa;
                continue;
            }
            if (dfn[y] == -1) {
                dfs(y, x);
                low[x] = std::min(low[x], low[y]);
            } else {
                low[x] = std::min(low[x], dfn[y]);
            }
        }

        if (dfn[x] == low[x]) {
            int y;
            do {
                y = q[r--];
                bel[y] = cntBlock; 
            } while (y != x);
            cntBlock += 1;
        }
    }

public:
    // original graph
    std::vector<int> dfn, low, bel, cutDeg;
    std::set<std::pair<int, int>> S_bridge; 

    // shrinking graph
    std::vector<std::vector<int>> g;//就是由割边组成的无根树
    //g.size() - 1就是割边数量
    int cntBlock = 0, componentNum = 0;

    EdgeBC(const std::vector<std::vector<int>> &e)
        : e(e), dfn(e.size(), -1), low(e.size()), bel(e.size(), -1), cutDeg(e.size()) {
        int n = e.size();
        q.assign(n + 1, 0);

        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                componentNum += 1;
                dfs(i, -1);
            }
        }

        g.resize(cntBlock);
        for (int x = 0; x < n; x++) {
            for (int y : e[x]) {
                if (bel[x] == bel[y])
                    continue;
                g[bel[x]].push_back(bel[y]);
                S_bridge.emplace(x, y); S_bridge.emplace(y, x);//符合条件，加入集合
            }
        }
    }
};