更新日志
思路
割边定义与割点相似，不过是把点换成了边，所以思想和割点差不多。
我们只需要在Tarjan过程中判断某一颗子树的low是否严格大于当前节点的dfn。值得注意，这里子树的low不应该由到它的原边回溯到它的父节点得到！
究其原因，其实就是如果子树是一个强连通分量，那么这条连接这个子结点的边就连接了两个强连通分量。
另一个解释，子结点无法通过别的边回到父节点或其上，那么这条边就是唯一一条连接子结点与父节点的边，也就是割边。（因此不能走原边更新low）。
这样就可以得到割边了。
细节
如何判断一条边是不是原边呢？如果使用链式前向星存图，就很好解决。
众所周知，无向边存下来就是两个有向边，而我们都是连着储存的，所以只需要把编号除以 \(2\) 即可得到其无向边编号。
（如果和我一样习惯从 \(1\) 开始编号，可以：(e-1)/2+1）
模板
int dcnt;
int dfn[N],low[N];
bool bri[M];//判断是否是桥
void tarjan(int now,int fed){//记录父边编号
dfn[now]=low[now]=++cnt;
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(!dfn[nxt]){
tarjan(nxt,eid);
low[now]=min(low[now],low[nxt]);
if(low[nxt]>dfn[now]){
bri[eid]=true;
}
}else if(eid!=fed)low[now]=min(low[now],dfn[nxt]);
}
}
例题
注：割边通常与求边双联合使用，所以就直接放边双的例题了。
洛谷边双模板题
代码
前注：非题解，不做详细讲解
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> veci;
const int N=5e5+5,M=2e6+5;
int n,m;
int cnt;
int hd[N],to[M*2],ne[M*2];
void adde(int u,int v){
to[++cnt]=v;
ne[cnt]=hd[u];
hd[u]=cnt;
}
int dcnt;
int dfn[N],low[N];
bool bri[M];
void tarjan(int now,int fed){
dfn[now]=low[now]=++cnt;
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(!dfn[nxt]){
tarjan(nxt,eid);
low[now]=min(low[now],low[nxt]);
if(low[nxt]>dfn[now]){
bri[eid]=true;
}
}else if(eid!=fed)low[now]=min(low[now],dfn[nxt]);
}
}
int bcnt;
int bcc[N];
veci nods[N];
void dfs(int now){
bcc[now]=bcnt;
nods[bcnt].push_back(now);
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(bcc[nxt]!=0||bri[eid])continue;
dfs(nxt);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++){
cin>>a>>b;
adde(a,b);
adde(b,a);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,0);
}
for(int i=1;i<=n;i++){
if(!bcc[i]){
++bcnt;
dfs(i);
}
}
cout<<bcnt<<"\n";
for(int i=1;i<=bcnt;i++){
cout<<nods[i].size()<<" ";
for(auto j:nods[i])cout<<j<<" ";
cout<<"\n";
}
return 0;
}