POJ3352 Road Construction Tarjan+边双连通

时间:2022-08-31 18:52:54

题目链接:http://poj.org/problem?id=3352

题目要求求出无向图中最少需要多少边能够使得该图边双连通。

在图G中,如果任意两个点之间有两条边不重复的路径,称为“边双连通”,去掉任何一条边都是其他边仍然是连通的,也就是说边双连通图中没有割边。

算法设计是:运用tarjan+缩点。对于每一个边双连通分量,我们都可以把它视作一个点,因为low值相同的点处在同一个边双连通分量中,可以简单地思考一下,(u,v)之间有两条可达的路径,dfs一定可以从一条路开始搜索并且从另一条路回去。而边双连通分量最初开始搜索的一个点的编号就是这个边双连通分量的low值,因为假设这个点的low值更加靠前的话,他与之前的结点一定是边双连通的关系,有一条边搜索到这个点,这个点在之后还有一条不重合的路径能到达先前那个结点,与边双连通分量的最大性产生矛盾,其实我们也可以把那个点收纳进这个边连通分量,把它作为该连通分量第一个进入dfs树的结点。故有边双连通分量中的点low值相同。

最终将这些点变成一个新的点图,这个点图中最大的边双连通分量就是一个点,所以我们只要看在这张图中需要加多少条边可以使得它边双连通就行。可以证明使得缩点图边双连通加上的边数是 (1+度数为1的点的数量)/2。由于这些缩点的low值都是不同的,所以我们可以用low值作为degree(点的度数)的索引。计算度数的时候时候扫描所有的点,只要跟一个low值不同的点有边,那么该low值(缩点)一定有一个外界的度(可看成入度),最后统计最终的只有一个度的连通分量数量即可。

用下面这张图同样可以证明为什么边双连通分量中的dfs中更新low值为什么是代码中所说的那样一个过程,因为low[3]是等于1的,而3的dfs顺序,就是dfn[3]=3,到了五号结点的时候,我们发现有回退边(5,3)如果此时我们用3的dfn值来更新5的low值的话就会发现5的low是3,回溯之后发现1,2,3结点low值是1,而4,5结点的low值是3,这样真的正确吗?很遗憾是错误的,为什么呢?我们可以发现,是因为在五号结点访问边(5,3)的时候错过了3号节点的回退边(3,1)在边双连通分量的计算中,回退边是需要包括在内的,这样dfs搜索到这个点之后这个点可以通过多条回退边跳回一个low=dfn结点,这个结点的low值就是他要更新成为的值。故边双连通分量中low的计算可以说是十分简洁但是要区分开和其他tarjan算法的low值计算策略,主要tarjan的这个low值太牛逼了!!!包含了太多的信息orz

POJ3352 Road Construction Tarjan+边双连通

代码如下:

 #include<cstring>
#include<vector>
#include<stdio.h>
using namespace std;
const int maxn =;
int n,m,low[maxn],dfn;
vector<int>G[maxn];
void dfs(int u,int fa)//先用dfs处理处每个点的low值,以便相同的low值合并
{//处理low值时不需要处理dfn数组
low[u]=++dfn;
for(int i=;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa)continue;//保证dfs 树的前向性
if(!low[v])
dfs(v,u);
low[u]=min(low[u],low[v]);
}
}
int tarjan()
{
int degree[maxn];
memset(degree,,sizeof(degree));
for(int i=;i<=n;i++)
{
for(int j=;j<G[i].size();j++)
{
if(low[i]!=low[G[i][j]])
degree[low[i]]++;
}
}
int res=;
for(int i=;i<=n;i++)
{
if(degree[i]==)res++;
}
return res;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
int x,y;
memset(low,,sizeof(low));
for(int i=;i<=n;i++)G[i].clear();
while(m--)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfn=;//每次dfs之前设置dfs树的编号从1开始
dfs(,-);
int ans=tarjan();
printf("%d\n",(ans+)/);
}
return ;
}

POJ3352 Road Construction Tarjan+边双连通的更多相关文章

  1. POJ-3352 Road Construction&comma;tarjan缩点求边双连通!

    Road Construction 本来不想做这个题,下午总结的时候发现自己花了一周的时间学连通图却连什么是边双连通不清楚,于是百度了一下相关内容,原来就是一个点到另一个至少有两条不同的路. 题意:给 ...

  2. poj 3352 Road Construction【边双连通求最少加多少条边使图双连通&amp&semi;&amp&semi;缩点】

    Road Construction Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 10141   Accepted: 503 ...

  3. POJ3352 Road Construction(边双连通分量)

                                                                                                         ...

  4. &lbrack;POJ3352&rsqb;Road Construction

    [POJ3352]Road Construction 试题描述 It's almost summer time, and that means that it's almost summer cons ...

  5. POJ3352 Road Construction &lpar;双连通分量&rpar;

    Road Construction Time Limit:2000MS    Memory Limit:65536KB    64bit IO Format:%I64d & %I64u Sub ...

  6. POJ3352 Road Construction 双连通分量&plus;缩点

    Road Construction Description It's almost summer time, and that means that it's almost summer constr ...

  7. POJ 3352 Road Construction(边—双连通分量)

    http://poj.org/problem?id=3352 题意: 给出一个图,求最少要加多少条边,能把该图变成边—双连通. 思路:双连通分量是没有桥的,dfs一遍,计算出每个结点的low值,如果相 ...

  8. poj 3177 Redundant Paths(tarjan边双连通)

    题目链接:http://poj.org/problem?id=3177 题意:求最少加几条边使得没对点都有至少两条路互通. 题解:边双连通顾名思义,可以先求一下连通块显然连通块里的点都是双连通的,然后 ...

  9. poj3352 Road Construction &amp&semi; poj3177 Redundant Paths (边双连通分量)题解

    题意:有n个点,m条路,问你最少加几条边,让整个图变成边双连通分量. 思路:缩点后变成一颗树,最少加边 = (度为1的点 + 1)/ 2.3177有重边,如果出现重边,用并查集合并两个端点所在的缩点后 ...

随机推荐

  1. SharePoint如何将使列表不被爬网爬到。

    有一个项目,没有对表单进行严格的权限管理,虽然用户在自己的首页只能看到属于的单子,但是在搜索的时候,所有人的单子都能被搜到,所以客户造成了困惑. 那么问题来了,怎么让列表或者文档库不被爬网爬到. 有两 ...

  2. Web 开发人员和设计师必读文章推荐【系列二十九】

    <Web 前端开发精华文章推荐>2014年第8期(总第29期)和大家见面了.梦想天空博客关注 前端开发 技术,分享各类能够提升网站用户体验的优秀 jQuery 插件,展示前沿的 HTML5 ...

  3. JavaScript正则表达式小记

    RegExp.html div.oembedall-githubrepos{border:1px solid #DDD;border-radius:4px;list-style-type:none;m ...

  4. 又折腾到这么晚 &comma; 图片Viewpager PagerIndicator&comma;listview 和侧边栏滑动的事件处理

    代码 思路 根据坐标判断 事件是否拦截 调用 getParent().requestDisallowInterceptTouchEvent(true);方法告诉上层ViewGroup 是否拦截 返回t ...

  5. ZigZag Conversion &lbrack;LeetCode&rsqb;

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like ...

  6. python&colon;redis简单操作

    一,安装redis-py pip install redis easy_install redis 二,简单用法 import redis # 连接redis服务器 def conn_redis(): ...

  7. Java Web整合开发&lpar;79&rpar; -- Struts 2

    一. Struts 2.x 概述 不继承任何类的Action Struts 2的Action并不一定要实现Action接口或者继承ActionSupport,任何POJO都可以做Action,只要这个 ...

  8. Leetcode&colon;Unique Binary Search Trees &amp&semi; Unique Binary Search Trees II

    Unique Binary Search Trees Given n, how many structurally unique BST's (binary search trees) that st ...

  9. 算法一之N皇后问题

    (写这篇文章主要是明天就要考试了,算法考试,今天不想再复习了,xiang着今天也开通了博客,于是在这个平台上进行复习,应该会更高效.最后祝愿我明天考个好成绩.嘻嘻...) n皇后问题,主要是应用到回溯 ...

  10. ●CodeForces 698C LRU

    题链: http://codeforces.com/problemset/problem/698/C题解.1: 概率dp,状压dp 棒棒哒题解:https://www.cnblogs.com/liu- ...