Coding Interview Problem - Critical Connections In Network

[@subee128]

Thank you

[@anonymoussloth6687]

Why do we need current time in DFS? Why can't we just set the time stamp of node 0 to some value and then in DFS, before we call DFS on the neighbour, just set the time stamp of the neighbour to 1 + time stamp of the current node. Basically, why do we need current_time when we can use time_stamp[current_node]?

[@KnapsackLabs]

Hi, this is a good question. Because timestamp[v] can be updated in the function call, it is not always true that timestamp[v] == current_timestamp. You are right that you don't necessarily need to store a current_timestamp variable, you could use timestamp[parent] + 1; however, you can't use timestamp[v]. I used it for convenience and code readability.

[@anonymoussloth6687]

@@KnapsackLabs i am still confused. Timestamp[parent] would also be updated right? Then why can we use that but not timestamp [v]? I am having trouble visualising it

[@KnapsackLabs]

@@anonymoussloth6687 Actually yeah you are right timestamp[parent] can also get updated. Hmm not too sure, but I still don't think that it changes the fact that you can't rely on timestamp[v] or timestamp[parent]. I think then it is required that you use a variable to store current_timestamp. Feel free to try using your method instead saving a current_timestamp though to see if it works! It personally didn't work for me, but maybe I am implementing it wrong.

[@anonymoussloth6687]

@@KnapsackLabs lol it didn't work for me either which is why i asked. But i think i get it now. Timestamp values get updated so we need to use the current time value in the DFS call. But what about that min operation? Why isn't that part of the if statement? Why is it outside?

[@KnapsackLabs]

@@anonymoussloth6687 The goal of the min operation is to set timestamps[v] = timestamps[neigh] when timestamps[neigh] < timestamps[v]. This happens when the connection between v and neigh is non-critical. The if statement holds true when timestamps[neigh] > curr_timestamp, meaning the connection between v and neigh is critical. Therefore if we move the min operation into the if statement it would not get to run when timestamps[neigh] < timestamps[v] which would lead to a incorrect answer.

[@blasttrash]

You jumped straight into the "idea" of using timestamps? Whats the reasoning behind this? Did you just see the solution posted by someone else and make a video? Or was there a natural thought process to this? You explained the thought process and stuff very naturally until you made a huge logical leap and jumped and into using timestamps without giving any insight into why you did so.