I am Learning Articulation points in Graph thoery which is an application of DFS.I wrote the code by taking reference from GeeksforGeeks [Atriculation Points].(Articulation Points (or Cut Vertices) in a Graph - GeeksforGeeks)
void dfs(int u)
{
static int time=0;
int child=0;
vis[u]=1;
dis_t[u]=low[u]=++time;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!vis[v])
{
child++;
parent[v]=u;
dfs(v);
low[u]=min(low[u],low[v]);
if(parent[u]==-1 and child>1)
{
AP[u]=1;
}
if(parent[u]!=-1 and low[v]>=dis_t[u])
AP[u]=1;
}
else if(v!=parent[u])
low[u]=min(low[u],dis_t[v]);
}
}
I came across two conditions.
a vertex u is articulation point if one of the following two conditions is true.
- u is root of DFS tree and it has at least two children.
- u is not root of DFS tree and it has a child v such that no vertex in subtree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.
First condition is clear,but I can’t understand the second one.
What is the use of low[u]=min(low[u],low[v]);
Hoping some help:)