sql数据库的网站迁移,miy188coo免费入口,wordpress格行代码6,怎样下载网页的视频目录
预备知识
模板1#xff1a;无向图的桥
模板2#xff1a;无向图的割点
模板3#xff1a;有向图的强连通分量 讲之前先补充一下必要概念#xff1a;
预备知识
无向图的【连通分量】#xff1a; 即极大联通子图#xff0c;再加入一个节点就不再连通#xff08;对…目录
预备知识
模板1无向图的桥
模板2无向图的割点
模板3有向图的强连通分量 讲之前先补充一下必要概念
预备知识
无向图的【连通分量】 即极大联通子图再加入一个节点就不再连通对于非连通图一定两个以上的连通分量
无向图的【(割边或)桥】 即去掉该边图就变成了两个连通子图
无向图的【割点】 将该点和相关联的边去掉图将变成两个及以上的子图注意有割点不一定有桥但是有桥一定有割点 无向图的【边双连通图】: 无向图中不存在桥即删除一条边后仍然连通(每两个点间有至少两条路径且路径上的边互不重复) 无向图的【点双连通图】: 无向图中不存在割点删除一个点后仍然联通(顶点大于2时每两个点间有至少两条路径且路径上的点互不重复) 【边双连通分量eDDC】极大边双连通图 【点双连通分量vDDC】: 极大点双连通图 无向图的【缩点】1 把每个【eDDC】看成一个点桥看成连接两个点的无向边得到一棵树。这种方式称为eDCC缩点
无向图的【缩点】2 把每个【vDDC】看成一个点割点看成一个点每个割点向包含它vDDC连接一条边得到一棵树。这种方式称为vDCC缩点
有向图的【强连通分量】
即极大连通子图任何两个节点都能相互到达 模板1无向图的桥 首先介绍时间戳和回溯点我更喜欢叫它走回点听我往下分析
dfn[u] (时间戳) 表示u节点深度优先遍历最先访问的序号
low[u](走回点)表示u节点或子孙能走回到的最小节点序号。
给出结论
无向边x,y是桥当搜索树上存在x的某个子节点y满足 low[y]dfn[x]没有等号
怎么理解呢 首先就是你不能走父子边回去也就是怎么来的怎么回去这样肯定是不行的。我们必须要走非父子边回去的。因为当从非父子边能回去时也就意味着走到了环那么此时就获取能回到的最小dfn为low然后回溯时候父节点获取孩子更小的low即可。相当于走到环了那么把这个最小的dfn传遍整个环中也就是整个连通分量中。从而表示u节点或子孙能走回到的最小节点序号。这样的话同一个连通分量中low值是一样的是最早走回的点号看不懂可以画一下图就理解了
对于无向图的桥孩子的low值比父亲的dfn值大就说明有桥这个可怜的孩子不能走非父子边回家了能不可怜吗
void tarjan(int u,int fa){dfn[u]low[u]num;//初始化for(int ihead[u];i;ie[i].next){int ve[i].to;if(vfa) continue;//不可以走父子边回去if(!dfn[v]){//没访问过就递归访问访问完要更新lowtarjan(v,u);low[u]min(low[u],low[v]);//获取孩子最小的low值low是自己或子孙能走回的最小dfn嘛不是回溯if(low[v]dfn[u]){//孩子的low值比父亲的dfn值大说明有桥coutu- vis bridge \n;} }else{//可以从非父子边回去就要获取dfn值就是该点能回到的最小dfn不是回溯low[u]min(low[u],dfn[v]);}}
}
这段代码把“回溯大法”体现的很好。可以看到没访问过就递归访问返回后也就是等到孩子们的low值都变正确了我再去更新自己的low。
另外那一句else其实是留给遇环来处理的父亲节点根本用不上你只需要在孩子们遇环后把它们自己“照顾好了”之后借助它们的结果来优化自己就行了。 完整代码
#include bits/stdc.h//无向图的桥
using namespace std;
const int maxn10005;
int n,m;
int head[maxn],cnt;
struct node{int to,next;}e[maxn*2];
int low[maxn],dfn[maxn],num;
//dfn[u](时间戳)表示u节点深度优先遍历访问的序号
//low[u](走回点)表示u节点或子孙能走回到的最小节点序号void add(int u,int v){ e[cnt](node){v,head[u]};head[u]cnt;}
void tarjan(int u,int fa){dfn[u]low[u]num;//初始化for(int ihead[u];i;ie[i].next){int ve[i].to;if(vfa) continue;//不可以走父子边回去if(!dfn[v]){//没访问过就递归访问访问完要更新lowtarjan(v,u);low[u]min(low[u],low[v]);//获取孩子最小的low值low是自己或子孙能走回的最小dfn嘛不是回溯if(low[v]dfn[u]){//孩子的low值比父亲的dfn值大说明有桥coutu- vis bridge \n;} }else{//可以从非父子边回去就要获取dfn值就是该点能回到的最小dfn不是回溯low[u]min(low[u],dfn[v]);}}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));cntnum0;
}int main(){while(cinnm){init();int u,v;while(m--){cinuv;add(u,v);add(v,u);}for(int i1;in;i){//因为不一定整个图都联通所以要判断那些点是否走不到if(!dfn[i]) tarjan(i,i);//深度优先搜索树的起点就是树根}}
}可以输入数据或自己画图试一下 7 7 1 4 1 2 2 3 3 5 5 7 5 6 6 4 或 7 6 1 2 2 3 3 5 5 7 5 6 6 4 模板2无向图的割点
x是割点条件x不是根节点 且搜索树上存在x的一个子节点y满足low[y]dfn[x]
【或者】x是根节点 且搜索树上存在至少两个子节点满足上述条件 画图可证明这里不多说了
#include bits/stdc.h//无向图的割点
using namespace std;
const int maxn10005;
int n,m,root;
int head[maxn],cnt;
struct node{int to,next;}e[maxn*2];
int low[maxn],dfn[maxn],num;void add(int u,int v){ e[cnt](node){v,head[u]};head[u]cnt;}
void tarjan(int u,int fa){dfn[u]low[u]num;//初始化int count0;//记录有几个满足条件的子节点for(int ihead[u];i;ie[i].next){int ve[i].to;if(vfa) continue;//没访问过就递归访问访问完更新lowif(!dfn[v]){tarjan(v,u);low[u]min(low[u],low[v]);//low是自己或子孙能走回的最小dfnif(low[v]dfn[u]){count;if(u!root||count1)coutuis gepoint \n;} }else{//可以从非父子边回去就要获取dfn值low[u]min(low[u],dfn[v]);}}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));cntnum0;
}int main(){while(cinnm){init();int u,v;while(m--){cinuv;add(u,v);add(v,u);}for(int i1;in;i){//因为不一定整个图都联通所以要判断那些点是否走不到if(!dfn[i]) {rooti;tarjan(i,i);}}}
}
测试数据供你参考使用 7 7 1 4 1 2 2 3 3 5 5 7 5 6 6 4 或 5 3 1 2 2 3 3 5 模板3有向图的强连通分量
有向图的【强连通分量】即极大连通子图任何两个节点都能相互到达
if(low[u]dfn[u]){//在回溯之前在low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是一个连通分量int v;do{//输出强连通分量一定要先执行再判断vs.top();s.pop();coutV: v ;ins[v]0;}while(v!u);//直到和自己不等为止cout\n;}
前面和无向图基本一样无非不用跳过走父子边步骤后面内容就不太一样了。
判断条件在low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是一个连通分量。
#include bits/stdc.h//有向图的强连通分量
using namespace std;
const int maxn10005;
bool ins[maxn];
int n,m;
int head[maxn],cnt;
stack int s;
struct node{int to,next;}e[maxn*2];
int low[maxn],dfn[maxn],num;void add(int u,int v){ e[cnt](node){v,head[u]};head[u]cnt;}void tarjan(int u){dfn[u]low[u]num;//dfn访问序号low使能回溯到的最早的dfnins[u]1;s.push(u);//第一次访问节点时候入栈for(int ihead[u];i;ie[i].next){int ve[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]min(low[u],low[v]);//获取孩子的最小的low值 }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){//在回溯之前在low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是一个连通分量int v;do{//输出强连通分量一定要先执行再判断vs.top();s.pop();coutV: v ;ins[v]0;}while(v!u);//直到和自己不等为止cout\n;}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(ins,0,sizeof(ins));memset(dfn,0,sizeof(dfn));cntnum0;
}int main(){while(cinnm){init();int u,v;while(m--){cinuv;add(u,v);}for(int i1;in;i){//有向图不一定整个图都双向联通所以要判断那些点是否走不到if(!dfn[i]) tarjan(i);}}
}
参考数据 5 8 1 2 1 3 3 2 3 4 3 5 4 1 4 5 5 1
