POJ - 3177 Redundant Paths (边双连通缩点)

时间:2022-08-31 18:47:39

题意:在一张图中最少可以添加几条边,使其中任意两点间都有两条不重复的路径(路径中任意一条边都不同)。

分析:问题就是最少添加几条边,使其成为边双连通图。可以先将图中所有边双连通分量缩点,之后得到的就是一棵树。

那么问题又转化成为:在这棵树上添加几条边使其成为一个双连通分量。答案是缩点之后(leaf+1)/2,其中leaf是树的叶节点个数。

具体方法为,首先把两个最近公共祖先最远的两个叶节点之间连接一条边,这样可以把这两个点到祖先的路径上所有点收缩到一起,因为一个形成的环一定是双连通的。然后这样不断一对一地找完,次数正好是(leaf+1)/2次。
#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 (边双连通缩点)的更多相关文章

  1. POJ 3177 Redundant Paths &lpar;边双连通&plus;缩点&rpar;

    <题目链接> <转载于 >>>  > 题目大意: 有n个牧场,Bessie 要从一个牧场到另一个牧场,要求至少要有2条独立的路可以走.现已有m条路,求至少要新 ...

  2. poj 3177 Redundant Paths&lpar;边双连通分量&plus;缩点&rpar;

    链接:http://poj.org/problem?id=3177 题意:有n个牧场,Bessie 要从一个牧场到另一个牧场,要求至少要有2条独立的路可以走.现已有m条路,求至少要新建多少条路,使得任 ...

  3. POJ 3177 Redundant Paths 边双(重边)缩点

    分析:边双缩点后,消环变树,然后答案就是所有叶子结点(即度为1的点)相连,为(sum+1)/2; 注:此题有坑,踩踩更健康,普通边双缩短默认没有无向图没有重边,但是这道题是有的 我们看,low数组是我 ...

  4. POJ 3352 Road Construction ; POJ 3177 Redundant Paths (双联通)

    这两题好像是一样的,就是3177要去掉重边. 但是为什么要去重边呢??????我认为如果有重边的话,应该也要考虑在内才是. 这两题我用了求割边,在去掉割边,用DFS缩点. 有大神说用Tarjan,不过 ...

  5. POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)

    POJ 3177 Redundant Paths POJ 3352 Road Construction 题目链接 题意:两题一样的.一份代码能交.给定一个连通无向图,问加几条边能使得图变成一个双连通图 ...

  6. tarjan算法求桥双连通分量 POJ 3177 Redundant Paths

    POJ 3177 Redundant Paths Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12598   Accept ...

  7. POJ 3177 Redundant Paths(边双连通的构造)

    Redundant Paths Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 13717   Accepted: 5824 ...

  8. poj 3177 Redundant Paths【求最少添加多少条边可以使图变成双连通图】【缩点后求入度为1的点个数】

    Redundant Paths Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11047   Accepted: 4725 ...

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

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

随机推荐

  1. QT QML目录导航列表视图

    [功能] /目录.文件 /文件过滤 /递归 /事件 /高亮当前行 /当前选项 /目录切换动画 /限制根目录 [下载]:http://download.csdn.net/detail/surfsky/8 ...

  2. JavaScript中this的一些怪异现象

    <!--JavaScript伪协议和内联事件对于this的指向不同--> <a href="#" onclick="alert(this.tagName ...

  3. C&num;----我对坐标系的理解和图形转动

    目录: 设置图形的旋转 设置坐标轴的反向 图形的旋转 参考一个文章:http://www.bccn.net/Article/kfyy/vc/jszl/200601/3008.html ; 目标:让Dr ...

  4. NOIP欢乐模拟赛 T1 解题报告

    小澳的方阵 (matrix.cpp/c/pas) [题目描述] 小澳最近迷上了考古,他发现秦始皇的兵马俑布局十分有特点,热爱钻研的小澳打算在电脑上还原这个伟大的布局. 他努力钻研,发现秦始皇布置兵马俑 ...

  5. Node&period;js学习&lpar;14&rpar;----EJS模板引擎

    这个入门教程将从以下几个方面来讲解: 1. 引入EJS 2. 创建一个模板 3. 使用视图工具组件 4. 使用错误处理组件 5. 什么情况下应使用EJS 引入EJS 在我们正式开始前,我们先来做点准备 ...

  6. 基于NIOS-II的示波器:PART3 初步功能实现

    本文记录了在NIOS II上实现示波器的第三部分. 本文主要包括:硬件部分的BRAM记录波形,计算频率的模块,以及软件部分这两个模块的驱动. 本文所有的硬件以及工程参考来自魏坤示波仪,重新实现驱动并重 ...

  7. Android远程桌面助手&lpar;B1332&rpar;之文件管理器

    Android远程桌面助手除了支持Android界面的显示及控制外,还支持Android文件系统的管理,包括文件的快速上传(push).下拉(pull)和查看(cat). Android远程桌面助手( ...

  8. heroku 部署ruby项目后 未连接数据库显示(We&&num;39&semi;re sorry&comma; but something went wrong&period; If you are the application owner )

    如何部署请参照: http://blog.csdn.net/xz360717118/article/details/62422741 部署后如果发现显示:We're sorry, but someth ...

  9. C&num;&period;NET股票历史数据采集,【附18年历史数据和源代码】

    阅读目录 1.数据采集需求 2.股市数据接口 3.数据库设计 4.关键信息采集 5.源代码和数据库 如果用知乎,可以关注专栏:.NET开源项目和PowerBI社区 重点重点:我没有买股票,没有买股票, ...

  10. lintcode-14-二分查找

    二分查找 给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1. 样例 在数组 ...