题意:在一张图中最少可以添加几条边,使其中任意两点间都有两条不重复的路径(路径中任意一条边都不同)。
分析:问题就是最少添加几条边,使其成为边双连通图。可以先将图中所有边双连通分量缩点,之后得到的就是一棵树。
那么问题又转化成为:在这棵树上添加几条边使其成为一个双连通分量。答案是缩点之后(leaf+1)/2,其中leaf是树的叶节点个数。
#include<iostream>
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn =5e4+;
struct Edge{
int to,next;
}edges[maxn<<];
bool instack[maxn];
int bccno[maxn],head[maxn],dfn[maxn],low[maxn],degree[maxn],clk,top,scc;
stack<int> S; void init()
{
clk = top = scc =;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(bccno,,sizeof(bccno));
memset(instack,,sizeof(instack));
memset(degree,,sizeof(degree));
} void AddEdge(int u,int v)
{
edges[top].to = v;
edges[top].next =head[u];
head[u] = top++;
} void Tarjan(int u,int id)
{
int v;
low[u]=dfn[u]=++clk;
S.push(u);
instack[u]=true;
for(int i=head[u];i!=-;i=edges[i].next){
v = edges[i].to;
if(i==(id^)) continue;
if(!dfn[v]){
Tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]= min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){ //找到一个双连通分量
scc++; //从1开始
int x;
while(true){
x =S.top();S.pop();
bccno[x]=scc; //确定分量编号
instack[x]=false;
if(x==u) break; //找到了自己就要停止标号
}
}
} int main()
{
int N,M,v,u,tmp;
while(~scanf("%d%d",&N,&M)){
init();
for(int i=;i<M;++i){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
Tarjan(,-);
for(int i=;i<=N;++i){
for(int j =head[i];j!=-;j=edges[j].next){
v = edges[j].to;
if(bccno[i]!=bccno[v]){ //根据分量编号缩点,计算度
degree[bccno[i]]++;
}
}
}
int res=;
for(int i=;i<=scc;++i){
if(degree[i]==)
res++;
}
printf("%d\n",(res+)/);
}
return ;
}
POJ - 3177 Redundant Paths (边双连通缩点)的更多相关文章
-
POJ 3177 Redundant Paths (边双连通+缩点)
<题目链接> <转载于 >>> > 题目大意: 有n个牧场,Bessie 要从一个牧场到另一个牧场,要求至少要有2条独立的路可以走.现已有m条路,求至少要新 ...
-
poj 3177 Redundant Paths(边双连通分量+缩点)
链接:http://poj.org/problem?id=3177 题意:有n个牧场,Bessie 要从一个牧场到另一个牧场,要求至少要有2条独立的路可以走.现已有m条路,求至少要新建多少条路,使得任 ...
-
POJ 3177 Redundant Paths 边双(重边)缩点
分析:边双缩点后,消环变树,然后答案就是所有叶子结点(即度为1的点)相连,为(sum+1)/2; 注:此题有坑,踩踩更健康,普通边双缩短默认没有无向图没有重边,但是这道题是有的 我们看,low数组是我 ...
-
POJ 3352 Road Construction ; POJ 3177 Redundant Paths (双联通)
这两题好像是一样的,就是3177要去掉重边. 但是为什么要去重边呢??????我认为如果有重边的话,应该也要考虑在内才是. 这两题我用了求割边,在去掉割边,用DFS缩点. 有大神说用Tarjan,不过 ...
-
POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
POJ 3177 Redundant Paths POJ 3352 Road Construction 题目链接 题意:两题一样的.一份代码能交.给定一个连通无向图,问加几条边能使得图变成一个双连通图 ...
-
tarjan算法求桥双连通分量 POJ 3177 Redundant Paths
POJ 3177 Redundant Paths Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 12598 Accept ...
-
POJ 3177 Redundant Paths(边双连通的构造)
Redundant Paths Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13717 Accepted: 5824 ...
-
poj 3177 Redundant Paths【求最少添加多少条边可以使图变成双连通图】【缩点后求入度为1的点个数】
Redundant Paths Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11047 Accepted: 4725 ...
-
poj 3177 Redundant Paths(tarjan边双连通)
题目链接:http://poj.org/problem?id=3177 题意:求最少加几条边使得没对点都有至少两条路互通. 题解:边双连通顾名思义,可以先求一下连通块显然连通块里的点都是双连通的,然后 ...
随机推荐
-
QT QML目录导航列表视图
[功能] /目录.文件 /文件过滤 /递归 /事件 /高亮当前行 /当前选项 /目录切换动画 /限制根目录 [下载]:http://download.csdn.net/detail/surfsky/8 ...
-
JavaScript中this的一些怪异现象
<!--JavaScript伪协议和内联事件对于this的指向不同--> <a href="#" onclick="alert(this.tagName ...
-
C#----我对坐标系的理解和图形转动
目录: 设置图形的旋转 设置坐标轴的反向 图形的旋转 参考一个文章:http://www.bccn.net/Article/kfyy/vc/jszl/200601/3008.html ; 目标:让Dr ...
-
NOIP欢乐模拟赛 T1 解题报告
小澳的方阵 (matrix.cpp/c/pas) [题目描述] 小澳最近迷上了考古,他发现秦始皇的兵马俑布局十分有特点,热爱钻研的小澳打算在电脑上还原这个伟大的布局. 他努力钻研,发现秦始皇布置兵马俑 ...
-
Node.js学习(14)----EJS模板引擎
这个入门教程将从以下几个方面来讲解: 1. 引入EJS 2. 创建一个模板 3. 使用视图工具组件 4. 使用错误处理组件 5. 什么情况下应使用EJS 引入EJS 在我们正式开始前,我们先来做点准备 ...
-
基于NIOS-II的示波器:PART3 初步功能实现
本文记录了在NIOS II上实现示波器的第三部分. 本文主要包括:硬件部分的BRAM记录波形,计算频率的模块,以及软件部分这两个模块的驱动. 本文所有的硬件以及工程参考来自魏坤示波仪,重新实现驱动并重 ...
-
Android远程桌面助手(B1332)之文件管理器
Android远程桌面助手除了支持Android界面的显示及控制外,还支持Android文件系统的管理,包括文件的快速上传(push).下拉(pull)和查看(cat). Android远程桌面助手( ...
-
heroku 部署ruby项目后 未连接数据库显示(We&#39;re sorry, but something went wrong. If you are the application owner )
如何部署请参照: http://blog.csdn.net/xz360717118/article/details/62422741 部署后如果发现显示:We're sorry, but someth ...
-
C#.NET股票历史数据采集,【附18年历史数据和源代码】
阅读目录 1.数据采集需求 2.股市数据接口 3.数据库设计 4.关键信息采集 5.源代码和数据库 如果用知乎,可以关注专栏:.NET开源项目和PowerBI社区 重点重点:我没有买股票,没有买股票, ...
-
lintcode-14-二分查找
二分查找 给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1. 样例 在数组 ...