割点和桥
程序员文章站
2022-04-15 12:41:15
...
算法大概:
dfn[v]记录的是节点v被访问的深度,low[v]记录的是点v可以到达的访问时间最早的祖先
在深度遍历图的过程中,记录下每个节点的深度,对当前节点u,以及和它相连的节点v,有两种情况。
(1).v没被访问过,这是递归访问节点v,并用i的可以到达的最早祖先来更新u的low值。
(2).v被访问过,这时说明有一个环,用v的深度来更新u的low值。
u是割点的条件:u是根且有大于一个的儿子,或者u不是根,且u有一个儿子v使得low[v]>=dfn[u]。
(u,v)是桥的条件:low[v]>dfn[u]
附上代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=2e5+5;
struct edge{
int u,v,next;
};
edge edges[maxm];
int head[maxn],tot;
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void add_edges(int u,int v)
{
edges[tot].u=u;
edges[tot].v=v;
edges[tot].next=head[u];
head[u]=tot++;
}
int n,m,dfn[maxn],low[maxn],t;
bool cut[maxn],brige[maxm];
void dfs(int u,int f)
{
dfn[u]=low[u]=t++;
int child=0;
for(int i=head[u];~i;i=edges[i].next){
int v=edges[i].v;
if(!dfn[v]){
dfs(v,u);
child++;
low[u]=min(low[u],low[v]);
if((f==-1&&child>1)||(f!=-1&&low[v]>=dfn[u])){
cut[u]=true;
}
if(low[v]>dfn[u]){
brige[i]=true;
}
}else if(v!=f){
low[u]=min(low[u],dfn[v]);
}
}
}
int main()
{
init();
scanf("%d%d",&n,&m);
int a,b;
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
add_edges(a,b);
add_edges(b,a);
}
t=1;
dfs(0,-1);
for(int i=0;i<n;i++){
if(cut[i]){
cout<<i<<endl;
}
}
for(int i=0;i<tot;i++){
if(brige[i]){
printf("%d %d\n",edges[i].u,edges[i].v);
}
}
return 0;
}
上一篇: c语言经典例子
下一篇: PHP3中使用ORACLE函数的使用说明
推荐阅读
-
从7点到9点写的小程序(用了模块导入,python终端颜色显示,用了点局部和全局可变和不可变作用域,模块全是自定义)
-
Mybatis结果集和实体类映射的一个小知识点
-
Oracle 和 mysql的9点区别
-
饿了么集点返红包是什么? 饿了么集点返红包参与和使用方法
-
vue项目创建步骤 和 路由router知识点
-
光猫桥接模式和路由模式哪个更好? 桥接模式和路由模式的区别
-
axios和ajax的区别点总结
-
使用foreach和volist标签分别实现模板数据的分页显示-2018年6月1日11点30分
-
jQuery相册管理和Ajax入门案例-2018年4月10日18点11分
-
id和name那个是用来标记锚点的标准用法?_html/css_WEB-ITnose