http://blog.csdn.net/geniusluzh/article/details/6619575
在说Tarjan算法解决桥和边双连通分量问题之前我们先来回顾一下Tarjan算法是如何求解强连通分量的。 Tarjan算法在求解强连通分量的时候,通过引入dfs过程中对一个点访问的顺序dfsNum(也就是在访问该点之前已经访问的点的个数)和一个点可以到达的最小的dfsNum的low数组,当我们遇到一个顶点的dfsNum值等于low值,那么该点就是一个强连通分量的根。因为我们在dfs的过程中已经将点仍入到栈中,因此我们只需要将栈中的元素出栈直到遇到根,那么这些点就组成一个强连通分量。 对于边双连通分量,我们需要先了解一些概念: 边连通度:使一个子图不连通所需要删除的最小的边数就是该图的边连通度。 桥(割边):当删除一条边就使得图不连通的那条边称为桥或者是割边。 边双连通分量:边连通度大于等于二的子图称为边双连通分量。 理解了这些概念之后我们来看看Tarjan是如何求解边双连通分量的,不过在此之前我们先说说Tarjan是怎样求桥的。同样引入了dfsNum表示一个点在dfs过程中所被访问的时间,然后就是low数组表示该点最小的可以到达的dfsNum。我们分析一下桥的特点,删除一条边之后,那么如果dfs过程中的子树没有任何一个点可以到达父亲节点及父亲节点以上的节点,那么这个时候子树就被封死了,这条边就是桥。有了这个性质,也就是说当我们dfs过程中遇到一条树边a->b,并且此时low[b]>dfsNum[a],那么a-b就是一座桥。 呵呵桥都求出来了,还怕边双连通分量吗?我们把所有的桥去掉之后那些独立的分量就是不同的边双连通分量,这个时候就可以按照需要灵活的求出边双连通分量了。 下面附上POJ 3352的解题思路吧: 这道题的意思是说,给你一个无向图,然后问你至少需要添加几条边,可以使整个图变成边双连通分量,也就是说任意两点至少有两条路可以互相连通。我们这样考虑这个问题,属于同一个边双连通分量的任意点是至少有两条通路是可以互相可达的,因此我们可以将一个边双连通分量缩成一个点。然后考虑不在边双连通分量中的点,通过缩点后形成的是一棵树。对于一个树型的无向图,需要添加(度为1的点的个数+1)/2条边使得图成为双连通的。这样问题就是变成缩点之后,求图中度为1的点的个数了。 这个题目的条件给的很强,表示任意两个点之间不会有重边,因此我们可以直接经过Tarjan的low值进行边双连通分量的划分,最后求出度为1点数就可以解决问题了。如果是有重边的话,那么不同的low值是可能是属于同一个边双连通分量的,这个时候就要通过将图中的桥去掉然后求解边双连通分量,这个请见我的博客的另外一篇解题报告。 下面贴上POJ 3352的ac代码,供网友们参考:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
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;i<top[a];i++)
{
if(edge[a][i]!=fa)
{
if(dfsNum[edge[a][i]]==0)
{
tarjan(edge[a][i],a);
if(low[a]>low[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<=n;i++)
{
a=i;
for(j=0;j<top[i];j++)
{
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("%d\n",ans);
}
return 0;
}
上面的代码的写法确实有问题,因为在同一个双连通分量中的点的low值并不一定相等,所以使用low值来判断是否在同一个分量中显然是有问题的。因此我们最安全的做饭时在tarjan的过程中,把桥标记出来,然后使用dfs跑每一个连通分量,最后使用桥统计每个点的度。 对于上面的问题,给大家带来的误导,非常抱歉。 下面的代码是对上面代码的修改,写的有点乱,供大家分享一下。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
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;i<top[a];i++)
{
if(edge[a][i]!=fa)
{
if(dfsNum[edge[a][i]]==0)
{
tarjan(edge[a][i],a);
if(low[a]>low[edge[a][i]])
low[a]=low[edge[a][i]];
if(dfsNum[a] < low[edge[a][i]])
{
exist[a][edge[a][i]] = exist[edge[a][i]][a] = true;
}
}
else
{
if(low[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 %d\n", 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])
{
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("%d\n",ans);
}
return 0;
}
Tarjan算法求解桥和边双连通分量(附POJ 3352 Road Construction解题报告)的更多相关文章
-
【边双连通】poj 3352 Road Construction
http://poj.org/problem?id=3352 [题意] 给定一个连通的无向图,求最少加多少条边使得这个图变成边双连通图 [AC] //#include<bits/stdc++.h ...
-
POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
POJ 3177 Redundant Paths POJ 3352 Road Construction 题目链接 题意:两题一样的.一份代码能交.给定一个连通无向图,问加几条边能使得图变成一个双连通图 ...
-
POJ 3352 Road Construction(边双连通分量,桥,tarjan)
题解转自http://blog.csdn.net/lyy289065406/article/details/6762370 文中部分思路或定义模糊,重写的红色部分为修改过的. 大致题意: 某个企业 ...
-
POJ 3352 Road Construction (边双连通分量)
题目链接 题意 :有一个景点要修路,但是有些景点只有一条路可达,若是修路的话则有些景点就到不了,所以要临时搭一些路,以保证无论哪条路在修都能让游客到达任何一个景点 思路 :把景点看成点,路看成边,看要 ...
-
POJ 3352 Road Construction(边—双连通分量)
http://poj.org/problem?id=3352 题意: 给出一个图,求最少要加多少条边,能把该图变成边—双连通. 思路:双连通分量是没有桥的,dfs一遍,计算出每个结点的low值,如果相 ...
-
POJ 3177 Redundant Paths &; POJ 3352 Road Construction(双连通分量)
Description In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numb ...
-
poj 3352 Road Construction【边双连通求最少加多少条边使图双连通&;&;缩点】
Road Construction Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 10141 Accepted: 503 ...
-
POJ 3352 Road Construction 双联通分量 难度:1
http://poj.org/problem?id=3352 有重边的话重边就不被包含在双连通里了 割点不一定连着割边,因为这个图不一定是点连通,所以可能出现反而多增加了双连通分量数的可能 必须要用割 ...
-
poj 3352 Road Construction(边双连通分量+缩点)
题目链接:http://poj.org/problem?id=3352 这题和poj 3177 一样,参考http://www.cnblogs.com/frog112111/p/3367039.htm ...
随机推荐
-
HTML中一些基本的标签用法
姓名输入框:<input type="text" value="默认有值"/> 密码输入框:<input type="text&qu ...
-
收集的maven 仓库地址(maven repository)
maven 仓库地址: 共有的仓库http://repo1.maven.org/maven2/http://repository.jboss.com/maven2/http://repository. ...
-
Ubuntu安装Tcpdump
参考:ubuntu下安装Tcpdump并使用 请先安装libpcap等,可以参照上文链接. 安装: 网址:http://www.tcpdump.org/ 解压: tar -zxvf tcpdump-4 ...
-
BIP_开发案例10_BI Publisher报表国际化多语言的实现(案例)
2014-12-26 Created By BaoXinjian
-
Ubuntu12.04安装java6
按照android官方文档 http://source.android.com 下载编译android源代码,jdk安装失败,尝试一下方法成功(2013-11-20) 下面我就把在Ubuntu12.0 ...
-
POJ 3074 Sudoku (Dancing Links)
传送门:http://poj.org/problem?id=3074 DLX 数独的9*9的模板题. 具体建模详见下面这篇论文.其中9*9的数独怎么转化到精确覆盖问题,以及相关矩阵行列的定义都在下文中 ...
-
应聘.net开发工程师常见的面试题(二)(转载)
1.公司要求开发一个继承System.Windows.Forms.ListView类的组件,要求达到以下的特殊功能:点击ListView各列列头时,能按照点击列的每行值进行重排视图中的所有行 (排序的 ...
-
final, finally, finalize的区别
1.final 用于声明属性,方法和类,分别表示属性不可变,方法不可覆盖,类不可继承. 内部类要访问局部变量,局部变量必须定义成final类型 2.finally是异常处理语句结构的一部分,表示总是执 ...
-
Android使用 selector 自定义控件背景 (以spinner 为例)
1. 在drawable中设置背景spinner_style.xml 文件 如图: 2. 在 styles.xml 中添加该背景 3. 最后在 spinner 控件添加样式 4.参考 http:// ...
-
openerp 产品图片的批量写入
Write a short python script which loops over the image files, encode with base64 and write to OpenER ...