.. index:: 无向图的边双连通分量

`无向图的边双连通分量 <https://www.luogu.com.cn/problem/P8436>`_
================================================================

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

    边双连通具有传递性，即，若 ``x`` , ``y`` 边双连通， ``y`` , ``z`` 边双连通，则 ``x`` , ``z`` 边双连通。

    划分双连通分量的关键在于寻找分量之间的衔接点，在边双连通分量中就是寻找 ``桥`` 。

    在无向图中，寻找 ``桥`` 其实很简单，若一个点通过某一条边后找不到路径（不包括反向边）返回原点，这条边就是 ``桥``。

    具体实现建议使用 ``tarjan`` 算法，以下是我对该算法的部分理解。

    ``tarjan`` 算法需要维护一些信息：

    - ``dfn[]`` ， ``low[]`` ， ``timestamp`` ，通过维护遍历的 ``dfn`` 序，记录每个点访问的时间戳，配合上 ``low[]`` 就可以得到该点接着往下遍历能达到的最小的时间戳。显然如果得到的时间戳比访问该点的时间戳更靠前，那么该点所经过的这条边必不可能是 ``桥``。
    
    - ``stk[]`` ， ``top`` ，使用栈来存储同一个边双连通分量的点。
    
    - ``bcc_cnt`` ， ``vector<int> bcc[]`` ，维护边双连通分量的个数和边双连通分量的点集。
   
    - ``is_brage[]`` ，判断边是否为 ``桥`` 。
  
    算法的核心部分：

    .. code-block:: CPP

        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (dfn[u] < low[v]) is_brage[i] = is_brage[i ^ 1] = true;
        } else if (i != (f ^ 1))
            low[u] = min(low[u], low[v]);

    ``!dfn[v]`` 和 ``i != (f ^ 1)`` 分支必须有 ``low[u] = min(low[u], low[v]);`` 这里不多做解释。

    关键在于下面两点：

    - ``if (dfn[u] < low[v]) is_brage[i] = is_brage[i ^ 1] = true;`` ``dfn[u] < low[v]`` 代表着经过这条边绕不回原点，可以判断该边为桥（任意无向边都由两条相反方向的有向边表示，由于边的id从0开始，若一条边的id等于另一条边id异或1，那么它们就是代表同一条无向边）。

    - ``i != (f ^ 1)`` 只有回去的边不是来时的边的反向边，才能更新能到达的最小时间戳。当然这个分支也代表着不会接着往下遍历了。

    具体代码：

    .. code-block:: CPP

        #include <cstring>
        #include <iostream>
        #include <vector>

        using namespace std;

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

        int n, m;

        int idx, e[M], ne[M], h[N];

        void add(int u, int v) { e[idx] = v, ne[idx] = h[u], h[u] = idx++; }

        int dfn[N], low[N], timestamp;
        int stk[N], top;
        int bcc_cnt;
        vector<int> bcc[N];
        bool is_brage[M];

        void tarjan(int u, int f) {
            dfn[u] = low[u] = ++timestamp;
            stk[++top] = u;

            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (!dfn[v]) {
                    tarjan(v, i);
                    low[u] = min(low[u], low[v]);
                    if (dfn[u] < low[v]) is_brage[i] = is_brage[i ^ 1] = true;
                } else if (i != (f ^ 1))
                    low[u] = min(low[u], low[v]);
            }

            if (dfn[u] == low[u]) {
                ++bcc_cnt;
                int t;
                do {
                    t = stk[top--];
                    bcc[bcc_cnt].push_back(t);
                } while (t != u);
            }
        }

        int main() {
            memset(h, -1, sizeof(h));

            cin >> n >> m;

            while (m--) {
                int u, v;
                cin >> u >> v;
                add(u, v);
                add(v, u);
            }

            for (int i = 1; i <= n; i++) {
                if (!dfn[i]) tarjan(i, -1);
            }

            cout << bcc_cnt << '\n';

            for (int i = 1; i <= bcc_cnt; i++) {
                cout << bcc[i].size();
                for (int j = 0; j < bcc[i].size(); j++) {
                    cout << ' ' << bcc[i][j];
                }
                cout << '\n';
            }

            return 0;
        }