最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 在说TarjanTarjan算法解决桥和边双连通分量问题

    在说 Tarjan 的算法解决桥接和边双连通分量的问题之前,我们先来回顾一下 Tarjan 的算法是如何解决强连通分量的。

    Tarjan的算法在求解强连通分量时,引入了阶dfsNum(即访问该点之前已经访问过的点数)和一个点在dfs过程中可以到达的最小dfsNum的low数组。,当我们遇到一个dfsNum值等于low值的顶点时,那么这个点就是一个强连通分量的根。因为我们在dfs的过程中已经把点入栈了,所以只需要弹出栈中的元素,直到遇到根,那么这些点就形成了一个强连通分量。

    对于边双连通组件,我们需要先了解一些概念:

    边连通性:使子图断开连接所需的最小边数是图的边连通性。

    桥(切边):删除边时,使图不连贯的边称为桥或切边。

    边双连通分量:边连通性大于等于二的子图称为边双连通分量。

    了解了这些概念之后,我们来看看 Tarjan 是如何解决边缘双连通组件的,不过在此之前,我们先来说说 Tarjan 是如何找到桥的。还引入了dfsNum来表示dfs过程中某个点被访问的时间,然后低位数组表示该点的最小可达dfsNum。我们来分析一下桥的特点。删除一条边后,如果dfs进程中的子树中没有点可以到达父节点和父节点之上的节点,那么此时子树被阻塞。这条边是桥。有了这个性质,也就是说当我们在dfs过程中遇到一个树边a->b,而此时low[b]>dfsNum[a],那么ab就是一个桥。

    哈哈,桥已经求好了,你还怕双连组件吗?在我们移除所有桥之后,那些独立的组件是不同的边缘双连通组件。这时,我们可以根据需要灵活找到边缘双连通分量。

    以下是POJ 3352的解题思路:

    这道题的意思是说,给你一个无向图,然后要求你加至少几条边c语言无向图连通分量,使整个图成为边双连通分量,也就是说任意两点至少有两条路径可以相互连接。. 我们这样考虑这个问题,属于同一个边双连通分量的任何点至少有两条相互可达的路径,因此我们可以将一个边双连通分量收缩为一个点。然后考虑不在边的双连通分量中的点,通过这些点后形成一棵树。对于一个树形的无向图,需要添加(度为1+1)/2条边的点的个数,使图双连通。问题是求它之后的图的度数成为一个收缩点。

    这道题的条件很强,说明任意两点之间都不会有双边c语言无向图连通分量,所以我们可以直接通过Tarjan的低值来划分边的双连通分量,最后求出1点的度数解决问题。如果有多个边,那么不同的低值可能属于同一个边双连通分量。这时,我们需要去掉图中的桥,然后求解边双连通分量。请参阅我博客的另一部分。问题解决报告。

    POJ 3352的ac代码贴在下面,供网友参考:

    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    const int Max=1010;
    int top[Max],edge[Max][Max];//memset(top,0,sizeof(top));
    int dfsNum[Max],dfsnum;//memset(dfsNum,0,sizeof(dfsNum)),dfsNum=1;
    int low[Max];
    int degree[Max];
    int ans;
    void tarjan(int a,int fa)
    {
        dfsNum[a]=low[a]=++dfsnum;
        for(int i=0;ilow[edge[a][i]])
                        low[a]=low[edge[a][i]];
                }
                else
                {
                    if(low[a]>dfsNum[edge[a][i]])
                        low[a]=dfsNum[edge[a][i]];
                }
      //          if(low[edge[a][i]]>dfsNum[a])
      //          {
       //         }
            }
        }
    }
    int solve(int n)
    {
        int i,j;
        int a,b;
        for(i=1;i
            {
                b=edge[a][j];
                if(low[a]!=low[b])
                {
                    degree[low[a]]++;
                    degree[low[b]]++;
                }
            }
        }
        int leaves=0;
        for(i=1;i<=n;i++)
        {
            if(degree[i]==2)
            {
                leaves++;
            }
        }
        return (leaves+1)/2;
    }
    int main()
    {
        int n,m;
        int i,a,b;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
            memset(top,0,sizeof(top));
            memset(degree,0,sizeof(degree));
            for(i=0;i<m;i++)
            {
                scanf("%d %d",&a,&b);
                edge[a][top[a]++]=b;
                edge[b][top[b]++]=a;
            }
            memset(dfsNum,0,sizeof(dfsNum));
            dfsnum=0;
            tarjan(1,-1);
            ans=solve(n);
            printf("%dn",ans);
        }
        return 0;
    }
    

    上面代码的写法确实有问题,因为点在同一个双连通分量中的低值不一定相等,所以用低值来判断它们是否在同一个分量中显然是有问题的. 所以,我们在做菜的时候,在tarjan过程中标记bridge,然后用dfs运行每个连通的组件,最后用bridge统计每个点的度数是最安全的。

    对于上述问题的误导,我深表歉意。

    下面的代码是对上面代码的修改,分享的有点乱。

    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    const int Max=1010;
    int top[Max],edge[Max][Max];//memset(top,0,sizeof(top));
    int dfsNum[Max],dfsnum;//memset(dfsNum,0,sizeof(dfsNum)),dfsNum=1;
    int low[Max];
    
    int degree[Max];
    int ans;
    bool exist[Max][Max];
    void tarjan(int a,int fa)
    {
        dfsNum[a]=low[a]=++dfsnum;
        for(int i=0;ilow[edge[a][i]])
                        low[a]=low[edge[a][i]];
                    if(dfsNum[a] dfsNum[edge[a][i]])
                        low[a]=dfsNum[edge[a][i]];
                }
            }
        }
    }
    int cc[Max], ccCnt;
    void dfs(int fa, int u)
    {
        cc[u] = ccCnt;
        for(int i=0; i<top[u]; i++)
        {
            int v = edge[u][i];
            if(v != fa && !exist[u][v] && !cc[v])
            {
               // printf("v %dn", v);
                dfs(u, v);
            }
        }
    }
    int solve(int n)
    {
        int i,j;
        int a,b;
        memset(cc, 0, sizeof(cc));
        ccCnt = 1;
        for(i=1; i<=n; i++)
        {
            if(!cc[i])
            {
    

    c语言无向图连通分量_c语言建立一个赋权图_c语言 无重复随机数

    dfs(-1, i); ccCnt++; } } //cout<<"ccCnt "<<ccCnt<<endl; for(i=1;i<=n;i++) { a=i; for(j=0;j<top[i];j++) { b=edge[a][j]; if(cc[a] != cc[b]) { degree[cc[a]]++; degree[cc[b]]++; } } } int leaves=0; for(i=1;i<ccCnt;i++) { if(degree[i]==2) { leaves++; } } return (leaves+1)/2; } int main() { int n,m; int i,a,b; while(scanf("%d %d",&n,&m)!=EOF) { memset(top,0,sizeof(top)); memset(degree,0,sizeof(degree)); for(i=0;i<m;i++) { scanf("%d %d",&a,&b); edge[a][top[a]++]=b; edge[b][top[b]++]=a; } memset(dfsNum,0,sizeof(dfsNum)); dfsnum=0; memset(exist, false, sizeof(exist)); tarjan(1,-1); ans=solve(n); printf("%dn",ans); } return 0; }

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 在说TarjanTarjan算法解决桥和边双连通分量问题

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论