For **articulation point and bridge** these following code is shown in *"Competitive Programming-1: Steven Halim"* (yes edition-1 because it is free):-

void articulationPointAndBridge(int u) { dfs_low[u] = dfs_num[u] = dfsNumberCounter++; // dfs_low[u] <= dfs_num[u] for (int j = 0; j < (int)AdjList[u].size(); j++) { ii v = AdjList[u][j]; if (dfs_num[v.first] == DFS_WHITE) { // a tree edge dfs_parent[v.first] = u; if (u == dfsRoot) rootChildren++; // special case, count children of root articulationPointAndBridge(v.first); if (dfs_low[v.first] >= dfs_num[u]) // for articulation point articulation_vertex[u] = true; // store this information first if (dfs_low[v.first] > dfs_num[u]) // for bridge printf(" Edge (%d, %d) is a bridge\n", u, v.first); dfs_low[u] = min(dfs_low[u], dfs_low[v.first]); // update dfs_low[u] } else if (v.first != dfs_parent[u]) // a back edge and not direct cycle [1] dfs_low[u] = min(dfs_low[u], dfs_num[v.first]); // update dfs_low[u] <--------------- } }

My doubt is [1]..In this line why are we using

`dfs_low[u]=min(dfs_low[u], dfs_num[v.first]);`

Can anybody explain this..why are we using the`dfs_num`

value not the`dfs_low`

value in case of visited nodes? I mean what is wring with`dfs_low[u]=min(dfs_low[u], dfs_num[v.first]);`

?Second thing is when we are going in line [1] can't we say for sure that the

`v->first`

's`dfs_num`

is smaller than`dfs_num`

of`u`

? (`dfs_num`

is also considered as the dfs discovery time).Third one is for verification--- In the bridge discovery case the condition is

`if (dfs_low[v.first] > dfs_num[u])`

because we have to find another node among the child of`u`

whose`dfs_low`

is strictly greater than`dfs_num`

otherwise we will select a single node as an edge --which is wrong! Is this line of logic correct?

Note: If anybody has any key insight in this algorithm he/she may help others (me also) users by posting it.

**UPD-1:** I have studied and searched about bridge tree and bridges. But no tutorial clearly states the answer of my questions. So anybody having any idea is requested to post here.

I have actually tried to think on these questions but couldn't get any possible reason for doubt-1..

Try to read this https://en.wikipedia.org/wiki/Biconnected_component, and maybe the references in the article... When you do not know an algorithm first thing you have to do is search the internet for references, and then if something does not clear, then ask .. is very easy to use google...

FYI, i found the GeeksforGeeks quite helpful in understanding the above concepts. You can also implement Tarjan's algorithm for finding connected components in directed graphs after learning about artriculation points and bridges. Here is the geeks for geeks article. Also you can try this problem for articulation points