割边（Bridge）

在图论中，割边（Bridge）是指在一个无向图中，如果删除某条边会导致图的连通分量数量增加，那么这条边就被称为割边。换句话说，割边是连接两个不同连通分量的边。

性质

1. 连通性：删除割边会使得图的连通性降低，即原本连通的节点变得不连通。
2. 无向图：割边的概念主要应用于无向图。
3. 桥的检测：可以使用Tarjan算法来检测图中的割边。

Tarjan算法检测割边

Tarjan算法是一种深度优先搜索（DFS）算法，用于检测图中的割边和强连通分量。以下是Tarjan算法检测割边的基本步骤：

1. 初始化：

   • 为每个节点设置一个时间戳（dfn）和一个追溯值（low）。
   • 使用一个栈来记录访问的节点。

2. DFS遍历：

   • 从任意一个节点开始进行DFS遍历。
   • 对于每个节点，记录其访问时间戳（dfn）和追溯值（low）。
   • 对于每个节点的邻接节点，如果邻接节点未被访问过，则递归访问，并更新当前节点的追溯值（low）。
   • 如果邻接节点的追溯值（low）大于当前节点的时间戳（dfn），则当前边是割边。

3. 割边判定：

   • 如果 low[v] > dfn[u]，则边 (u, v) 是割边。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m;
vector<PII> g[N];
int dfn[N],low[N],idx;
vector<int> bridge;
stack<int> stk;
vector<int> scc[N];
int cnt;
void tarjan(int u,int id)
{
    dfn[u]=low[u]=++idx;
    stk.push(u);
    for(auto j : g[u])
    {
        int v=j.first,id2=j.second;
        if(!dfn[v]) tarjan(v,id2);
        if(id!=id2) low[u]=min(low[u],low[v]);
    }
    if(low[u]==dfn[u])
    {
        bridge.push_back(id);
        cnt++;
        while(1)
        {
            int t=stk.top();
            stk.pop();
            scc[cnt].push_back(t);
            if(t==u) break;
        }
    }
    
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
     
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i,-1);
    }
    //for(auto i : bridge) cout<<i<<" ";
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        cout<<scc[i].size()<<" ";
        for(auto j : scc[i])
        {
            cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
} 
## 示例代码

以下是一个使用C++实现的Tarjan算法检测割边的示例代码：

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;
typedef pair<int, int> PII;

int n, m;
vector<PII> g[N];
int dfn[N], low[N], idx;
bool is_bridge[N];

void tarjan(int u, int p) {
    dfn[u] = low[u] = ++idx;
    for (auto &e : g[u]) {
        int v = e.first, id = e.second;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                is_bridge[id] = true;
            }
        } else if (v != p) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, -1);
    }
    for (int i = 1; i <= m; i++) {
        if (is_bridge[i]) {
            cout << "Edge " << i << " is a bridge." << endl;
        }
    }
    return 0;
}

我的模版：
题目

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m;
vector<PII> g[N];
int dfn[N],low[N],idx;
vector<int> bridge;
stack<int> stk;
vector<int> scc[N];
int cnt;
void tarjan(int u,int id)
{
    dfn[u]=low[u]=++idx;
    stk.push(u);
    for(auto j : g[u])
    {
        int v=j.first,id2=j.second;
        if(!dfn[v]) tarjan(v,id2);
        if(id!=id2) low[u]=min(low[u],low[v]);
    }
    if(low[u]==dfn[u])
    {
        bridge.push_back(id);
        cnt++;
        while(1)
        {
            int t=stk.top();
            stk.pop();
            scc[cnt].push_back(t);
            if(t==u) break;
        }
    }
    
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
     
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i,-1);
    }
    //for(auto i : bridge) cout<<i<<" ";
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        cout<<scc[i].size()<<" ";
        for(auto j : scc[i])
        {
            cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
}