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 thedfs_num
value not thedfs_low
value in case of visited nodes? I mean what is wring withdfs_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
'sdfs_num
is smaller thandfs_num
ofu
? (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 ofu
whosedfs_low
is strictly greater thandfs_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...