文档章节

图论:双连通分支-边

o
 osc_1ee7cxmx
发布于 2018/08/06 16:48
字数 960
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

POJ3177:利用Tarjan求无向图的边双连通分支

连通图去掉所有的桥(割边)之后,剩下的就是一块儿一块儿的边双连通分支了

那么这道题的描述是给定无向图G,问至少加入多少条边才能让原图成为一个双连通图

这个题的做法是利用Tarjan求出图中的所有桥,以桥为界限分出来的就是一个一个边的双连通分量

然后要做的是缩点,把所有的双连通分量缩成点,这样做了之后,会形成一棵树

那么答案要求至少要添加多少条边才能让原图成为双连通图,只要把树的叶子节点都连接起来就好了

我们最少要连的边=(叶子节点数+1)/2

这个题在初识的时候可以看成Tarjon强连通缩点和Tarjon求桥的一个结合

更深入的认识等以后总结的时候再说

int n,m,cnt,deep,bridge,sum,top,ans;
int g[maxn],dfn[maxn],low[maxn],col[maxn],vis[maxn],st[maxn],deg[maxn];
struct Edge{int t,next;bool cut;}e[maxm];

col在这里面是双连通块儿,deg是点的度数,用来统计缩点图(这里是树)的叶子结点

inline int change(int x)
{
    if(x%2==0)
        x--;
    else
        x++;
    return x;
}

然后双向边加入的时候是正好一奇一偶,如果初始边的编号为0,的话,亦或1就好了,如果初始为1 就要这么处理一下子

然后是Tarjan,无向图版本的

void tarjan(int u,int fa)
{
    dfn[u]=++deep;low[u]=deep;
    vis[u]=1;
    st[++top]=u;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)
    {
        int v=e[tmp].t;if(v==fa) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                bridge++;
                e[tmp].cut=true;
                int tmp1=change(tmp);
                e[tmp1].cut=true;
            }
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        col[u]=++sum;vis[u]=0;
        while(st[top]!=u)
        {
            col[st[top]]=sum;
            vis[st[top--]]=0;
        }
        top--;
    }
}

然后是缩点和统计结果的过程

for(u=1;u<=n;u++)
            for(int tmp=g[u];tmp;tmp=e[tmp].next)
                if(e[tmp].cut) deg[col[u]]++;
        for(int i=1;i<=sum;i++)
            if(deg[i]==1) ans++;
        printf("%d\n",(ans+1)/2);

给出完整实现:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 const int maxn=5005;
 5 const int maxm=20005;
 6 using namespace std;
 7 int n,m,cnt,deep,bridge,sum,top,ans;
 8 int g[maxn],dfn[maxn],low[maxn],col[maxn],vis[maxn],st[maxn],deg[maxn];
 9 struct Edge{int t,next;bool cut;}e[maxm];
10 void addedge(int u,int v)
11 {
12     e[++cnt].t=v;e[cnt].next=g[u];e[cnt].cut=0;
13     g[u]=cnt;
14 }
15 inline int change(int x)
16 {
17     if(x%2==0)
18         x--;
19     else
20         x++;
21     return x;
22 }
23 void tarjan(int u,int fa)
24 {
25     dfn[u]=++deep;low[u]=deep;
26     vis[u]=1;
27     st[++top]=u;
28     for(int tmp=g[u];tmp;tmp=e[tmp].next)
29     {
30         int v=e[tmp].t;if(v==fa) continue;
31         if(!dfn[v])
32         {
33             tarjan(v,u);
34             low[u]=min(low[u],low[v]);
35             if(low[v]>dfn[u])
36             {
37                 bridge++;
38                 e[tmp].cut=true;
39                 int tmp1=change(tmp);
40                 e[tmp1].cut=true;
41             }
42         }
43         else if(vis[v]) low[u]=min(low[u],dfn[v]);
44     }
45     if(dfn[u]==low[u])
46     {
47         col[u]=++sum;vis[u]=0;
48         while(st[top]!=u)
49         {
50             col[st[top]]=sum;
51             vis[st[top--]]=0;
52         }
53         top--;
54     }
55 }
56 void init()
57 {
58     cnt=deep=bridge=sum=top=ans=0;
59     memset(g,0,sizeof(g));
60     memset(dfn,0,sizeof(dfn));
61     memset(low,0,sizeof(low));
62     memset(vis,0,sizeof(vis));
63     memset(st,0,sizeof(st));
64     memset(deg,0,sizeof(deg));
65     memset(e,0,sizeof(e));
66 }
67 int main()
68 {
69     int u,v;
70     while(scanf("%d%d",&n,&m)==2)
71     {
72         init();
73         while(m--)
74         {
75             scanf("%d%d",&u,&v);
76             addedge(u,v),addedge(v,u);
77         }
78         tarjan(1,0);
79         for(u=1;u<=n;u++)
80             for(int tmp=g[u];tmp;tmp=e[tmp].next)
81                 if(e[tmp].cut) deg[col[u]]++;
82         for(int i=1;i<=sum;i++)
83             if(deg[i]==1) ans++;
84         printf("%d\n",(ans+1)/2);
85     }
86     return 0;
87 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

unity列表控件Horizontal/Vertical/Grid Layout Group用法介绍

1. Grid Layout Group 为Panel控件添加Grid Layout Group,子控件为四个按钮,分别为Grid,Calendar,Gear,User: 默认属性为 为方便演示,按钮的底色为控件自带image,按钮上面的图标为其子...

路过暴风
20分钟前
19
0
Distinct()与lambda? - Distinct() with lambda?

问题: Right, so I have an enumerable and wish to get distinct values from it. 是的,所以我有一个可枚举的,并希望从中获得不同的值。 Using System.Linq , there's of course an ext......

法国红酒甜
25分钟前
8
0
学习编写编译器[关闭] - Learning to write a compiler [closed]

问题: Preferred languages : C/C++, Java, and Ruby. 首选语言 :C / C ++,Java和Ruby。 I am looking for some helpful books/tutorials on how to write your own compiler simply for......

技术盛宴
55分钟前
17
0
OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
今天
41
1
MySQL 常用操作

1 创建/打开/删除数据库 create database db;create database db character set utf8mb4;use db;drop database db;alter database db character set utf8mb4; 2 修复表 mysqlcheck --a......

氷泠
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部