decoder123's blog

By decoder123, 4 years ago, In English,

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

  1. 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]);?

  2. 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).

  3. 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.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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