边双学习笔记-白红宇的个人博客

边双学习笔记

发布日期：2021-08-13 22:07:48 浏览次数：7 分类：技术文章

本文共 3434 字，大约阅读时间需要 11 分钟。

什么是边双？

双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用。——百度百科

用人话来说，就是在无向图上以边为关键字，对原图缩点

为什么要学边双

与强连通分量类似，我们可以求出边双之后对原图缩点，使原图变为一个没有环的图，方便我们后续处理。

边双怎么写

跟强连通分量做法一模一样，唯一的不同就是我们在取low的时候要小心一下不能取父节点，以防之前取回去

//Luogu P2783 有机化学之神偶尔会做作弊//Nov,9th,2018//边双#include
      
       #include
       
        #include
        
         #include
         
          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 
          
            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
           
            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
            
             =0;i--) if(depth[x]-(1<
             
              =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

Code

例题：

这题我们只需要对原图做边双缩点之后LCA直接前缀和做就好。

//Luogu P2783 有机化学之神偶尔会做作弊//Nov,9th,2018//边双#include
      
       #include
       
        #include
        
         #include
         
          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 
          
            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
           
            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
            
             =0;i--) if(depth[x]-(1<
             
              =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

Code

转载于:https://www.cnblogs.com/GoldenPotato/p/9934377.html

转载地址：https://blog.csdn.net/weixin_30699831/article/details/98326215 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Linux vim快捷键

下一篇：Java基础之在窗口中绘图——使用模型/视图体系结构在视图中绘图（Sketcher 1 drawing a 3D rectangle）...

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

什么是边双？

为什么要学边双

边双怎么写

例题：

发表评论

最新留言

关于作者

推荐文章