首页 / 算法 / poj-3177（并查集+双联通分量+Tarjan算法）

poj-3177（并查集+双联通分量+Tarjan算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了poj-3177（并查集+双联通分量+Tarjan算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1584字，纯文字阅读大概需要3分钟。

内容图文

题目链接：传送门

思路：

题目要将使每一对草场之间都有至少两条相互分离的路径，所以转化为（一个有桥的连通图至少加几条边才能变为双联通图？）

先将桥删除，然后原图变为多个连通块，每一个连通块就是一个边双联通分量，将双联通子图收缩为一个顶点，再把桥边加回来，边连通度为1，

顺便统计度为1的节点的个数，即叶节点的个数即为cnt，所以至少在树上添加（cnt+1）/2条边。

技术分享图片 技术分享图片 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
usingnamespace std;
constint maxn = 10010;
struct Edge{
    int u,v;
};
Edge tmp;
vector <Edge> ee;
int num[maxn],vis[maxn],low[maxn],fa[maxn],tog[maxn],m,n,tim;
vector <int> vc[maxn];
void Init()
{
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    memset(low,0,sizeof(low));
    memset(fa,0,sizeof(fa));
    memset(tog,0,sizeof(tog));
    ee.clear();
    for(int i=0;i<maxn;i++) vc[i].clear();
    tim=1;
}
int MIN(int x,int y)
{
    return x<y?x:y;
}
int f(int x)
{
    if(fa[x]==0) return x;
    elsereturn fa[x]=f(fa[x]);
}
void Tarjan(int v,int pre)
{
    int i,w;
    vis[v]=1;
    low[v]=num[v]=tim++;
    for(i=0;i<vc[v].size();i++){
        w=vc[v][i];
        if(!vis[w]){
            Tarjan(w,v);
            low[v]=MIN(low[v],low[w]);
            if(low[w]>num[v]){
                tmp.u=v;tmp.v=w;
                ee.push_back(tmp);
            }
            else{
                int t1=f(v);
                int t2=f(w);
                if(t1!=t2) fa[t2]=t1;
            }
        }
        elseif(pre!=w) low[v]=MIN(low[v],num[w]);
    }
}
int main(void)
{
    int i,j,x,y;
    while(~scanf("%d%d",&n,&m)){
        Init();
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            vc[x].push_back(y);
            vc[y].push_back(x);
        }
        Tarjan(1,-1);
        for(i=0;i<ee.size();i++){
            int t1=f(ee[i].u);
            int t2=f(ee[i].v);
            tog[t1]++;tog[t2]++;
        }
        int cnt=0;
        for(i=1;i<=n;i++)
        if(tog[i]==1) cnt++;
        cnt=(cnt+1)/2;
        printf("%d\n",cnt);
    }
    return0;
}
View Code

 

原文：https://www.cnblogs.com/2018zxy/p/10357599.html

内容总结

以上是互联网集市为您收集整理的poj-3177（并查集+双联通分量+Tarjan算法）全部内容，希望文章能够帮你解决poj-3177（并查集+双联通分量+Tarjan算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1248422.html

来源：【匿名】