POJ 3352 Road Construction(边双连通分量)
http://poj.org/problem?id=3352
题意:给你一个连通的无向图,现在问你最少在该图中添加几条边,能使得该图变成边双连通图?
分体:解题思路参考以下博客:
http://blog.csdn.net/lyy289065406/article/details/6762370
首先如果该图本身就是一个边双连通图,我们就不需要添加边了.所以我们先要对该无向图用tarjan()函数求出图中所有的桥.
对于每个桥来说,它都是连接着两个不同的边双连通分量的.(尽管可能一个点也算是一个边双连通分量).对于同一个边双连通分量,我们有以下结论:low[i]值相同的点必定属于同一个边双连通分量.
且我们如果要添加一条边,我们必然在分别属于不同边双连通分量的两个点之间添加.我们如果在同一个边双连通分量内加边,没有任何意义.所以我们把求得所有桥之后的图简化:我们把每个边双连通分量看出一个缩点,然后用每条桥去连接每个缩点(即每个边双连通分量).如下例所示:
所以我们只需要在G图的缩点树上添加边使其变成一个边双连通图即可.这样操作我们能保证我们添加的边最少且最后的图是全局边双连通的.
那么我们对于一棵树需要添加几条边才能使得它变成边双连通的呢?
有以下结论:对于一棵无向树,我们要使得其变成边双连通图,需要添加的边数 == (树中度数为1的点的个数+1)/2
(以上结论不太好证明)
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
int n,m;
vector<int> G[maxn];
int dfs_clock;
int pre[maxn],low[maxn];
int degree[maxn];
int tarjan(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
if(!pre[v])
{
int lowv=tarjan(v,u);
lowu=min(lowu,lowv);
}
else if(pre[v]<pre[u])
lowu=min(lowu,pre[v]);
}
return low[u]=lowu;
}
int main()
{
scanf("%d%d",&n,&m);
dfs_clock=0;
memset(pre,0,sizeof(pre));
memset(degree,0,sizeof(degree));
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
tarjan(1,-1);//得出所有节点的low值,每个不同的low值代表一个边双连通分量
for(int u=1;u<=n;u++)//遍历每条边
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(low[u]!=low[v]) degree[low[v]]++;
}
int cnt=0;
for(int i=1;i<=n;i++)if(degree[i]==1)
cnt++;
printf("%d\n",(cnt+1)/2 );
}
分享到:
相关推荐
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
* 图的割边和割点:例如 poj3352。 * 最小割模型、网络流规约:例如 poj3308。 3. 数据结构: * 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态二叉检索树:例如 poj2482、poj2352。 * ...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
2. **Kruskal算法**:首先对所有边按照权重从小到大排序,然后依次考虑每条边,如果这条边连接的两个顶点不在已经选择的边构成的连通分量中,就将其加入到最小生成树中。 理解最小生成树的算法是解决这类问题的关键...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
- (poj3352):判定两个图是否同构。 6. **小世界模型**: - (poj3308,):探索社交网络中的小世界现象。 ### 九、数据结构进阶 1. **树状数组**: - (poj2528, poj2828, poj2777, poj2886, poj2750):一种高效...
标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标签】"POJ 1159 Palindrome" 标签明确了这是关于回文的一个问题,回文是指正读反读都能读通的字符串,例如"madam"或"12321"。在编程中,回文的检测是字符串处理的基本操作,常常涉及字符串反转和比较。 **知识点...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
- **定义**:在图中找到所有的双连通分量。 - **示例题目**: - poj2942 - **应用场景**:适用于图的连通性分析。 **6. 强连通分支及其缩点** - **定义**:找到图中的强连通分支并进行缩点。 - **示例题目**: - ...
根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...
- POJ 3352:最大流问题的求解。 ### 数据结构 #### 栈 - **题目示例**: - POJ 2528、POJ 2828:栈的基本操作与应用场景。 #### 队列 - **题目示例**: - POJ 2777、POJ 2886:队列的应用。 #### 树状数组 -...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告