Ehsan_sShuvo's blog

By Ehsan_sShuvo, history, 2 years ago, In English,

Could anyone please explain me clearly why we have to do

low[vertex]=min(low[vertex],dis[i]);

Yeah!I know that is for lowest discovery time determination.But my question is that all the time we put minimum time in the current node comparing with its adjacent nodes,but not increase the time.My question is two or more nodes cant visit at a time.But lowest time show that,it can do that.But how? Could anyone please clear me out?Actually,i read more than 5/6 resources,but i couldn't get that.There all says about subtree,ancestor,blah blah,but my memory couldn't make a sense for that,what they actually want to say.

Thanks in advance.

Following is the psuedocode of finding out articulation point.

time = 0
function DFS(adj[][], disc[], low[], visited[], parent[], AP[], vertex, V)
        visited[vertex] = true
        disc[vertex] = low[vertex] = time+1
        child = 0
        for i = 0 to V
                if adj[vertex][i] == true
                        if visited[i] == false
                                child = child + 1
                                parent[i] = vertex
                                DFS(adj, disc, low, visited, parent, AP, i, n, time+1)
                                low[vertex] = minimum(low[vertex], low[i])
                                if parent[vertex] == nil and child > 1
                                        AP[vertex] = true
                                if parent[vertex] != nil and low[i] >= disc[vertex]
                                        AP[vertex] = true
                        else if parent[vertex] != i
                                low[vertex] = minimum(low[vertex], disc[i])
 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

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

My question is two or more nodes cant visit at a time.But lowest time show that,it can do that.But how?

lowest time of a node denotes the discovery time of oldest ancestor which we can reach from this node. Two or more nodes can have the same oldest ancestor and hence same lowest time.
You can read my blog if it is still not clear to you.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically,i read your tutorial last night which i have found in hackerearth. but,thanks.

    Basically,i got that after watching a long tutorial what you said.BTW,thanks. Any link could you provide for Bridge?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great explanation

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

take a look on https://visualgo.net/en/dfsbfs i think u will be able to understand