什么是边双？
双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用Tarjan算法。——百度百科
用人话来说，就是在无向图上以边为关键字，对原图缩点
为什么要学边双
与强连通分量类似，我们可以求出边双之后对原图缩点，使原图变为一个没有环的图，方便我们后续处理。
边双怎么写
跟强连通分量做法一模一样，唯一的不同就是我们在取low的时候要小心一下不能取父节点，以防之前取回去
//Luogu P2783 有机化学之神偶尔会做作弊 //Nov,9th,2018 //边双 #include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while(!isdigit(c)){if(c=='-') f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int N=10000+100; vector <int> e[N],e2[N]; int low[N],dfn[N],dfn_to,mstack[N],top,belong[N],cnt; bool vis[N],InStack[N]; void Tarjan(int now,int fa) { low[now]=dfn[now]=++dfn_to; vis[now]=InStack[now]=true; mstack[++top]=now; for(int i=0;i<int(e[now].size());i++) if(vis[e[now][i]]==false) { Tarjan(e[now][i],now); low[now]=min(low[now],low[e[now][i]]); } else if(e[now][i]!=fa and InStack[e[now][i]]==true) low[now]=min(low[now],low[e[now][i]]); if(dfn[now]==low[now]) { cnt++; while(top>0) { InStack[mstack[top]]=false; belong[mstack[top--]]=cnt; if(mstack[top+1]==now) break; } } } int n,m; int fa[N][21],pre[N],depth[N]; void dfs(int now) { vis[now]=true; for(int i=1;i<=20;i++) fa[now][i]=fa[fa[now][i-1]][i-1]; for(int i=0;i<int(e2[now].size());i++) if(vis[e2[now][i]]==false) { depth[e2[now][i]]=depth[now]+1; fa[e2[now][i]][0]=now; pre[e2[now][i]]=pre[now]+1; dfs(e2[now][i]); } } int LCA(int x,int y) { if(depth[x]<depth[y]) swap(x,y); for(int i=20;i>=0;i--) if(depth[x]-(1<<i)>=depth[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void OutPut(int x) { if(x==0) { printf("0"); return; } int temp[50],ws=0; while(x>0) temp[++ws]=x%2,x/=2; for(int i=ws;i>=1;i--) printf("%d",temp[i]); } int main() { //freopen("2783.in","r",stdin); //freopen("2783.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) e[i].reserve(4), e2[i].reserve(4); for(int i=1;i<=m;i++) { int s=read(),t=read(); e[s].push_back(t); e[t].push_back(s); } Tarjan(1,1); for(int i=1;i<=n;i++) for(int j=0;j<int(e[i].size());j++) if(belong[i]!=belong[e[i][j]]) e2[belong[i]].push_back(belong[e[i][j]]); memset(vis,0,sizeof vis); pre[1]=1; dfs(1); int q=read(); for(int i=1;i<=q;i++) { int x=belong[read()],y=belong[read()],lca=LCA(x,y); int ans=pre[x]+pre[y]-pre[lca]; if(lca!=1) ans-=pre[fa[lca][0]]; OutPut(ans); printf(" "); //printf("%d ",ans); } return 0; }
例题：
luogu P2783 有机化学之神偶尔会做作弊
这题我们只需要对原图做边双缩点之后LCA直接前缀和做就好。
//Luogu P2783 有机化学之神偶尔会做作弊 //Nov,9th,2018 //边双 #include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while(!isdigit(c)){if(c=='-') f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int N=10000+100; vector <int> e[N],e2[N]; int low[N],dfn[N],dfn_to,mstack[N],top,belong[N],cnt; bool vis[N],InStack[N]; void Tarjan(int now,int fa) { low[now]=dfn[now]=++dfn_to; vis[now]=InStack[now]=true; mstack[++top]=now; for(int i=0;i<int(e[now].size());i++) if(vis[e[now][i]]==false) { Tarjan(e[now][i],now); low[now]=min(low[now],low[e[now][i]]); } else if(e[now][i]!=fa and InStack[e[now][i]]==true) low[now]=min(low[now],low[e[now][i]]); if(dfn[now]==low[now]) { cnt++; while(top>0) { InStack[mstack[top]]=false; belong[mstack[top--]]=cnt; if(mstack[top+1]==now) break; } } } int n,m; int fa[N][21],pre[N],depth[N]; void dfs(int now) { vis[now]=true; for(int i=1;i<=20;i++) fa[now][i]=fa[fa[now][i-1]][i-1]; for(int i=0;i<int(e2[now].size());i++) if(vis[e2[now][i]]==false) { depth[e2[now][i]]=depth[now]+1; fa[e2[now][i]][0]=now; pre[e2[now][i]]=pre[now]+1; dfs(e2[now][i]); } } int LCA(int x,int y) { if(depth[x]<depth[y]) swap(x,y); for(int i=20;i>=0;i--) if(depth[x]-(1<<i)>=depth[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void OutPut(int x) { if(x==0) { printf("0"); return; } int temp[50],ws=0; while(x>0) temp[++ws]=x%2,x/=2; for(int i=ws;i>=1;i--) printf("%d",temp[i]); } int main() { //freopen("2783.in","r",stdin); //freopen("2783.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) e[i].reserve(4), e2[i].reserve(4); for(int i=1;i<=m;i++) { int s=read(),t=read(); e[s].push_back(t); e[t].push_back(s); } Tarjan(1,1); for(int i=1;i<=n;i++) for(int j=0;j<int(e[i].size());j++) if(belong[i]!=belong[e[i][j]]) e2[belong[i]].push_back(belong[e[i][j]]); memset(vis,0,sizeof vis); pre[1]=1; dfs(1); int q=read(); for(int i=1;i<=q;i++) { int x=belong[read()],y=belong[read()],lca=LCA(x,y); int ans=pre[x]+pre[y]-pre[lca]; if(lca!=1) ans-=pre[fa[lca][0]]; OutPut(ans); printf(" "); //printf("%d ",ans); } return 0; }