POJ 3177 Redundant Paths(边双连通分量)
2024-09-01 18:13:54
【题目链接】 http://poj.org/problem?id=3177
【题目大意】
给出一张图,问增加几条边,使得整张图构成双连通分量
【题解】
首先我们对图进行双连通分量缩点,
那么问题就转化为给出一棵树,加边使得其成为边双连通分量的最小边数,
只要从叶节点连一条边到任意节点,那么就可以使得这个叶节点加入到双连通分量中,
那么优先叶节点和叶节点连接,所以其答案为(叶节点+1)/2
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N=5010,M=10010;
int e[M][2],cut[M],g[N],v[M<<1],nxt[M<<1],ed=1;
int f[N],dfn[N],low[N],num,cnt,from[N],d[N];
void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void tarjan(int x){
dfn[x]=low[x]=++num;
for(int i=g[x];i;i=nxt[i])if(!dfn[v[i]]){
f[v[i]]=i>>1,tarjan(v[i]);
if(low[x]>low[v[i]])low[x]=low[v[i]];
}else if(f[x]!=(i>>1)&&low[x]>dfn[v[i]])low[x]=dfn[v[i]];
if(f[x]&&low[x]==dfn[x])cut[f[x]]=1;
}
void dfs(int x,int y){
from[x]=y;
for(int i=g[x];i;i=nxt[i])if(!from[v[i]]&&!cut[i>>1])dfs(v[i],y);
}
int n,m;
int main(){
while(~scanf("%d%d",&n,&m)){
memset(g,0,sizeof(g));
memset(d,0,sizeof(d));
memset(from,0,sizeof(from));
memset(f,0,sizeof(f));
memset(cut,0,sizeof(cut));
num=0; ed=1; // 求边双连通分量时,ed一定要为1
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
e[i][0]=u; e[i][1]=v;
add(u,v);add(v,u);
}tarjan(1); cnt=0;
for(int i=1;i<=n;i++)if(!from[i])dfs(i,++cnt);
for(int i=1;i<=m;i++){
if(from[e[i][0]]!=from[e[i][1]]){
d[from[e[i][0]]]++;
d[from[e[i][1]]]++;
}
}int res=0;
//for(int i=1;i<=n;i++)printf("%d %d\n",from[i],d[i]);
for(int i=1;i<=n;i++)if(d[i]==1)res++;
printf("%d\n",(res+1)/2);
}return 0;
}
最新文章
- IBM Bluemix体验:Containers持久存储
- iOS开发——高级技术OC篇&;运行时(Runtime)机制
- Objective-C( Foundation框架 一 数组(NSMutableArray))
- unreal3之FName及潜在bug
- Linux下GCC的使用
- 【转】Android Studio -修改LogCat的颜色*美爆了*
- git使用中遇到的常见问题
- [Codeforces 501D] - Misha and Permutations Summation
- linux 内核头文件 linux kernel header
- DDS视图&;Button控件
- C++反汇编第一讲,认识构造函数,析构函数,以及成员函数
- 快速构建SPA框架SalutJS--项目工程目录 二
- redis 基本命令
- 酷!美国国家安全局(NSA)开源了逆向工程工具 Ghidra
- JS对Date的扩展,将 Date 转化为指定格式的String
- python 多线程笔记(5)-- 生产者/消费者模式
- LayoutInflater的动态增加控件
- 【luogu P4017 最大食物链计数】 题解
- HDU 1053 Entropy(哈夫曼编码 贪心+优先队列)
- es6,async简单总结
热门文章
- 洛谷P1273 有线电视网 (树上分组背包)
- HDU 1698 Just a Hook(线段树
- idea使用(一)
- Document base D:\devTools\apache-tomcat-6.0.51\webapps\AppService does not exist or is not a readable directory
- 51Nod 1118 机器人走方格--求逆元
- 组合数学--Polya 原理及典型应用
- mybatis基本流程、jdbc连接、ps:附mybatis(乐观锁)实现
- 【CF1027D】Mouse Hunt(拓扑排序,环)
- [bzoj4515][Sdoi2016]游戏-树链剖分+李超线段树
- bzoj 1016 深搜