zoj2588-tarjan求桥/割边
2024-10-08 19:24:59
tarjan求桥,算法流程详见核心代码:
void tarjan(int k){
dfn[k]=low[k]=++cnt;
//fa[k]=(edge){f,0,fid};
for(int i=head[k];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
fa[v]=e[i].id;//标记该边已走过,防止沿无向边返回
tarjan(v);
low[k]=min(low[v],low[k]);
}else
if(fa[k]!=e[i].id)low[k]=min(low[k],dfn[v]);//在不走无向边的情况下更新low
}
if(fa[k]&&low[k]==dfn[k])//若节点k的low=dfn则k在一个联通块中处于搜索树的顶部,那么节点k的父边一定为割边
ans[++na]=fa[k];
}
模板题:zoj2588
题目大意:给出一个无向图,按顺序输出割边序号。
好久没用zoj,PE几次,若无割边要加个判断,以免多输出个0
#include<cstring>
#include<cstdio>
#include<algorithm>
#define foru(i,x,y) for(int i=x;i<=y;i++)
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
const int N=;
struct edge{int to,nxt,id;}e[];
int head[N],dfn[N],low[N],ans[N],ne,na,cnt,n,m;
int fa[N];
void add(int a,int b,int c){
e[++ne]=(edge){b,head[a],c};head[a]=ne;
} void tarjan(int k){
dfn[k]=low[k]=++cnt;
//fa[k]=(edge){f,0,fid};
for(int i=head[k];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
fa[v]=e[i].id;//标记该边已走过,防止沿无向边返回
tarjan(v);
low[k]=min(low[v],low[k]);
}else
if(fa[k]!=e[i].id)low[k]=min(low[k],dfn[v]);//在不走无向边的情况下更新low
}
if(fa[k]&&low[k]==dfn[k])//若节点k的low=dfn则k在一个联通块中处于搜索树的顶部,那么节点k的父边一定为割边
ans[++na]=fa[k];
} int main(){
int T,u,v;
scanf("%d",&T);
while(T--){
clr(e);clr(head);clr(dfn);clr(low);clr(fa);clr(ans);
ne=na=cnt=;
scanf("%d%d",&n,&m);
foru(i,,m){
scanf("%d%d",&u,&v);
add(u,v,i);add(v,u,i);
}
foru(i,,n)
if(!dfn[i])tarjan(i);
sort(ans+,ans++na);
printf("%d\n",na);
if(na){
foru(i,,na-)printf("%d ",ans[i]);printf("%d\n",ans[na]);}
if(T)printf("\n");
}
return ;
}
最新文章
- <;转>;Unity3D研究院之C#使用Socket与HTTP连接服务器传输数据包
- mybatis批量插入返回主键问题
- RNN 入门教程 Part 3 – 介绍 BPTT 算法和梯度消失问题
- linux库列表
- linux下批量查找/替换文本内容
- jsp获取SessionID值
- Redis初步
- javascript算法挑战
- Qt的十六进制的控件
- 前端新人学习笔记-------html/css/js基础知识点(三)
- linux线程之pthread_join
- hdu2242(树形dp+tarjan+缩点)
- Bootstrap File Input的简单使用
- Python逻辑运算符
- css中单位px,em,rem和vh/vw的理解
- p1257 平面上最接近点对---(分治法)
- lumen----------A facade root has not been set.
- SQL注入之Sqli-labs系列第四十七关,第四十八关,第四十九关(ORDER BY注入)
- 浅谈C#堆栈与托管堆的工作方式(转)
- BZOJ3110 [Zjoi2013]K大数查询 树套树 线段树 整体二分 树状数组