边双连通分量学习笔记

· · 题解

传送门：模板题

前置知识：割边（桥），Tarjan 算法在无向图上的应用

概念就不介绍了。不知道概念来做模板题干什么。

做法：

首先，我们可以知道，一个边双连通分量内部一定不含有桥边，换句话说，内部不含有桥边的极大连通分量就是一个边双连通分量。

同时结合 Tarjan 算法的性质，栈顶到栈中一定有一段序列形成一个不含桥边的极大连通分量，我们就有了针对此题的做法。

主流做法是寻找所有的桥边，将其标记，然后用 dfs 求连通块，但是我这里要提供一种全新做法，它可以省略一遍 dfs，直接在 Tarjan 算法中就求出边双。

首先，让我们思考一个问题，如果在原图中，我们找到了桥边，便将栈中的元素全部出栈，作为一个边双连通分量，有可能会出现什么问题呢？（建议有了答案再往下看）

显然，你有可能会忽略掉你开始 dfs 的那个点所处的边双连通分量，因为你在初始的边双连通分量里找不到桥边。

这时，我们有两种解决方案:

  1. 建立一个超级点，将其与每个连通块相连，便可以保证原图中的每个边双连通分量都分配到一条桥边。连通块可以用并查集维护。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=5e6+5;
int n, m, q, tot, top, res, cnt;
int ver[M], nxt[M], head[M];
int dfn[N], stk[N], low[N];
int f[N], vis[N];
vector<int> g[N];
inline void add(int x,int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void tarjan(int x,int fa)
{
    bool f = 0;
    stk[++top] = x;
    dfn[x] = low[x] = ++res;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(!dfn[y])
        {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if(dfn[x] < low[y])//说明这条边是桥边
            {
                cnt++;
                while(stk[top+1] != y)
                    g[cnt].push_back(stk[top--]);//与点双不同，一个点只能存在于一个边双连通分量中
            }
        }
        else if(y != fa || f) low[x] = min(low[x], dfn[y]);
        if(y == fa) f = 1;
    }
}
int find(int k){return f[k] == k ? k : f[k] = find(f[k]);} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
        f[find(x)] = find(y);//统计连通块的代表
    }
    for(int i = 1; i <= n; i++)
    {
        int fi = find(i);
        if(!vis[fi])
            add(0, fi), vis[fi] = 1;//建立超级点
    }
    tarjan(0, 0);
    cout << cnt << '\n';
    for(int i = 1;i <= cnt; i++)
    {
        cout << g[i].size() << ' ';
        for(int j = 0; j < g[i].size(); j++)
            cout << g[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}
  1. 每次 Tarjan 结束后，便将栈清空，以统计你忽略掉的那个边双连通分量。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5, M = 5e6 + 5;
int n, m, q, tot, top, res, cnt;
int ver[M], nxt[M], head[M];
int dfn[N], stk[N], low[N];
int vis[N];
vector<int> g[N];
inline void add(int x,int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void tarjan(int x,int fa)
{
    bool f = 0;
    stk[++top] = x;
    dfn[x] = low[x] = ++res;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(!dfn[y])
        {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if(dfn[x] < low[y])
            {
                cnt++;
                while(stk[top+1] != y)
                    g[cnt].push_back(stk[top--]);
            }
        }
        else if(y != fa || f) low[x] = min(low[x], dfn[y]);
        if(y == fa) f = 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
        {
            tarjan(i, 0);
            cnt++;
            while(top)
                g[cnt].push_back(stk[top--]);
        }
    cout << cnt << '\n';
    for(int i = 1;i <= cnt; i++)
    {
        cout << g[i].size() << ' ';
        for(int j = 0; j < g[i].size(); j++)
            cout << g[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}