东营网站开发,免费网站推广方式,自助建站视频网站,wordpress function require割边#xff1a;dfn[u]low[v]
割点#xff1a;dfn[u]low[v] (若为根节点#xff0c;要有两个v这样的点) 一.知识点#xff1a;
1.连通#xff1a;
在图论中#xff0c;连通性是指一个无向图中的任意两个顶点之间存在路径。如果对于图中的任意两个顶点 u 和 vdfn[u]low[v]
割点dfn[u]low[v] (若为根节点要有两个v这样的点) 一.知识点
1.连通
在图论中连通性是指一个无向图中的任意两个顶点之间存在路径。如果对于图中的任意两个顶点 u 和 v存在一条路径从 u 到 v那么图被称为连通图。如果图不是连通的那么它可以被分为多个连通分量每个连通分量都是一个连通子图。
2.割点:
割点Cut Vertex也称为关节点或割顶是指在无向图中如果移除该顶点及其相连的边会导致图不再连通那么该顶点就被称为割点。
3.割边
割边Cut Edge也称为桥是指在无向图中如果移除该边会导致图不再连通那么该边就被称为割边。
割边在图中起到了连接不同连通分量的作用其移除会导致图的连通性发生变化。 4.tarjan算法选择性阅读 Tarjan算法是一种用于寻找有向图中强连通分量Strongly Connected Components简称SCC的算法由Robert Tarjan在1972年提出。强连通分量是指在有向图中任意两个顶点之间存在双向路径。
Tarjan算法使用深度优先搜索DFS来遍历图并通过维护一个栈和一些辅助数据结构来识别强连通分量。算法的基本思想是通过DFS遍历图中的每个顶点并为每个顶点记录其访问次序Discovery Time和能够回溯到的最早的祖先顶点Lowest Ancestor。通过这些信息可以识别出具有相同祖先的顶点集合即一个强连通分量。
Tarjan算法的步骤如下
对图中的每个顶点进行深度优先搜索DFS遍历。在DFS遍历的过程中为每个顶点记录其访问次序和最早祖先顶点。将已访问的顶点入栈。当DFS遍历回溯到一个顶点时检查该顶点的最早祖先顶点。如果最早祖先顶点是自身则将栈中的顶点弹出并将这些顶点构成一个强连通分量。重复步骤3和步骤4直到遍历完所有的顶点。
Tarjan算法的时间复杂度为O(VE)其中V是顶点数E是边数。它是一种高效的算法常被用于解决与强连通分量相关的问题如图的缩点、强连通分量的数量和结构等。
总之Tarjan算法是一种用于寻找有向图中强连通分量的算法通过DFS遍历和栈的运用可以高效地找到图中的所有强连通分量。 二.讲解
在此之前先介绍两个数组
int dfn[];里面存放访问顺序时间戳
int low[];里面存放追溯值即祖先节点最小的dfn
1割边
tarjan提出证明可以自行百度
当dfn[u]low[v]时连接这两条点的边为割边重边要特殊处理后面介绍
2割点 tarjan提出证明可以自行百度
当dfn[u]low[v]时u这个点为割点若为根节点要有两个v这样符合条件的点 三.割边
1题目 题目描述 找出割边 输入 第一行输入两个整数n和m表示点和边的个数。 第i(2i2m)行,每行输出两个数字表示一条边的两个点。 输出 割边 样例输入 6 7 1 2 1 3 2 4 2 5 3 4 4 5 4 6 样例输出 4---6 2初代码
/*
6 7
1 2
1 3
2 4
2 5
3 4
4 5
4 6
*/#includebits/stdc.h
#define maxn 100005
using namespace std;
int n,m;
struct Edge{int u,v,next;
}edge[maxn1];
int cnt,head[maxn];
void add(int u,int v){edge[cnt](Edge){u,v,head[u]}; head[u]cnt;
}
int num,dfn[maxn],low[maxn];
void tarjan(int u,int fa){dfn[u]low[u]num;for(int ihead[u];i;iedge[i].next){int vedge[i].v;if(vfa) continue;if(dfn[v]0){tarjan(v,u);low[u]min(low[u],low[v]);if(dfn[u]low[v]){ //割边条件 若则表示v不止和u相连 coutu----vendl; }}else{low[u]min(low[u],dfn[v]);}}
}
int main(){scanf(%d%d,n,m);int u,v;for(int i1;im;i){scanf(%d%d,u,v);add(u,v); add(v,u);}tarjan(1,0);return 0;
}
3bug与解答
1.若这张图有多个连通分量怎么办
答遍历即可 for(int i1;in;i){if(dfn[i]0) tarjan(1,0);}
2.若有重边怎么办结果显然不对。
答只continue第二次让这段代码运行 然后就无法满足 dfn[u]low[v]条件了 if(vfa){k; //防止重边 if(k1) continue;}
4最终代码
/*
6 7
1 2
1 3
2 4
2 5
3 4
4 5
4 6
*/#includebits/stdc.h
#define maxn 100005
using namespace std;
int n,m;
struct Edge{int u,v,next;
}edge[maxn1];
int cnt,head[maxn];
void add(int u,int v){edge[cnt](Edge){u,v,head[u]}; head[u]cnt;
}
int num,dfn[maxn],low[maxn];
void tarjan(int u,int fa){int k0;dfn[u]low[u]num;for(int ihead[u];i;iedge[i].next){int vedge[i].v;if(vfa){k; //防止重边 if(k1) continue;} if(dfn[v]0){tarjan(v,u);low[u]min(low[u],low[v]);if(dfn[u]low[v]){ //割边条件 若则表示v不止和u相连 coutu---vendl; }}else{low[u]min(low[u],dfn[v]);}}
}
int main(){scanf(%d%d,n,m);int u,v;for(int i1;im;i){scanf(%d%d,u,v);add(u,v); add(v,u);}//防止本来就有不连通的 for(int i1;in;i){if(dfn[i]0) tarjan(1,0);}return 0;
} 四.割点
其实只是微改动一下即可。其次就是可以优化一下。函数传参只需要传u无需判断是否为父节点。因为不会影响结果。自行参考代码推理
再次强调若为根节点要有两个v这样的点 参考代码
/*
6 7
1 2
1 3
2 4
2 5
3 4
4 5
4 6
*/#includebits/stdc.h
#define maxn 100005
using namespace std;
int n,m;
struct Edge{int u,v,next;
}edge[maxn1];
int cnt,head[maxn];
void add(int u,int v){edge[cnt](Edge){u,v,head[u]}; head[u]cnt;
}
int num,dfn[maxn],low[maxn],root;
void tarjan(int u){dfn[u]low[u]num;int flag0;for(int ihead[u];i;iedge[i].next){int vedge[i].v;if(dfn[v]0){tarjan(v);low[u]min(low[u],low[v]);if(dfn[u]low[v]){ //割点条件 if(u!root || flag1) coutu ;}}else{low[u]min(low[u],dfn[v]);}}
}
int main(){scanf(%d%d,n,m);int u,v;for(int i1;im;i){scanf(%d%d,u,v);add(u,v); add(v,u);}//防止本来就有不连通的 for(int i1;in;i){if(dfn[i]0){rooti;tarjan(i);} }return 0;
}
