G-55. Bridges in Graph - Using Tarjan's Algorithm of time in and low time

[@rushidesai2836]

Had to watch this 3 times to completely understand. Probably the most difficult of the playlist.

[@az-zm4ji]

haha same. my brain got messed up from this algo

[@Nutrino259]

I watched this video. And again cam back to watch this after 4 days. Now i clearly understand whole process!!!!!!!!!!

[@amansingh.h716]

thanks bro i am leaving this video

[@princeroshan4105]

Instead of using the conventional approach with DFS tree, subtree of DFS tree, and back edges, he's trying to explain it in an unconventional way, which doesn't seem appropriate for this context. However, I can't really argue, considering he works at Google.

[@venugopalreddy8596]

I think this problem is very hard to explain. But striver did it very clearly....Awesome!!

[@rohinianekar61]

Well, in simple words, if the low[] of next node is less than the one which calls dfs for it, then there is a other node through which that node can be reached and which appeared before the one which calls the dfs, Thanks, Well Explained❤

[@arpitkumarmishra2734]

kya bol rhe ho bhaya?

[@amitdahiya7425]

In Some details => if any adjacent node (except parent) has low time greater than curr node means node and adj node share an edge and the adj node is only reachable via this edge , so if we remove this edge we never gonna reach this adjNode , means this edge is a bridge

[@amitdahiya7425]

otherwise if low time is equal or lesser than curr node time , means that adjnode has other path which takes lesser or equal time than curr node , so if we try to remove this edge we still can reach the adjNode from other path , means they are still connected to each other , the edge is not a bridge

[@ABHIMANYUTHAPLIYAL]

had to spend too much time understanding it , now its clear. For those who could not understand this topic , i would suggest watch jenny lecture on bridges in graphs first, then come again to this lec, you will indeed have a lot more clarity.Because striver has explained it beautifully but to understand his approach you must know it from somewhere else before.

[@thaman701]

condition of critical edge why do we check lowest_time[recently popped node] > time[current node] and not lowest_time[current node]? pliz help bro

[@devanshverma8050]

@@thaman701 we won't be comparing with lowest_time[current node] because lowest_time[current node] might have got updated cuz of the adjacent nodes of current node , the thing to note here is that lowest_time[node] doesn't mean that u will take that much time to reach the "node" but it's rather keeps track of the earliest visited node reachable from the subtree rooted at "node" , so while comparing with lowest_time[recently popped node] tells that there might be node connected to it that can be reached earlier and through that further adjacent nodes , and if it's greater than the time[current node] , then there's no point cuz to reach that node u will be requiring that much time at least, and from the recently popped node if u r taking more than that then it's not even possible to reach lower time cuz all other paths will at least take more time than that.

[@thaman701]

@@devanshverma8050 thnxx bhai

[@shklbor]

zabardust bhai, nowhere is it as clearly explained as this. india is really vishav guru - we teach the entire world

[@schan263]

Thanks, I learned bridges before from a lengthy video somewhere and your video is a quick review and saves me lots of time.

[@kushjoshi9716]

It was hard first but then I watched the video twice and now I understand the problem. Striver is amazing!

[@40_arkoprovodatta23]

A visited array is not needed, if tin is initialized with -1, we could check if tin[i] == -1. Btw, an amazing explanation. ❤

[@cr7johnChan]

can u please tell me why my code does nt work for larger test cases vectorans; void dfs(int node,int dad,vector&low,vector&visited,vectorgraph[]){ visited[node]=1; low[node]=node; for(int j=0;jlow[node]) { ans.push_back({node,t}); } }else if(low[t]

[@TusharRaghav]

@@cr7johnChan your condition low[t] > low[node] is wrong, it should be low[t] > in[node]

[@praptib]

condition for bridge is low[node] > tin[neigh] and not low[node] > low[neigh] bcz for eg if node is 8, it can have low 3/6, and if neigh is 10, it can have low 3/6 so we can't compare lows of each other nor can we track just the current low and increment and decrement later as all nodes should be unique so tim array is used

[@ravisingh-el8np]

striver I know you teach good but just for this video sorry to say but this video is not much clear to a beginner like me and others also ,i watched jenny lecture and love babbar on this topic that was way more clearer. It's just a constructive feedback from one of your students. I watched your entire graph playlist but just for this video and articulation points video i had to refer others.

[@ajaybind6736]

this is only explanation can be for this tough question on youtube thanks striver !!

[@stith_pragya]

Understood, Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@huungryyyy]

Ok got it after watching twice but i guess it will take some time to digest .Thanku Striver Sir

[@mysteryman3737]

God!! How could you explain it so nicely.... Thank you so much for the explanation

[@kartikpal9141]

Insane stuff . So well explained

[@musharrafhussain130]

hell yeah! Finally completed the series. Thanks a lot Striver!

[@saillaanil2604]

the inititution is: the "tin" vector stores the steps/order in which we are visiting the nodes and the "low " vector is used to store the recent/(previously visited) node from which we can visit the current node. So if their is no previously visited to reach that node then it is a bridge.

[@skblabla]

You are so good at algorithms, hopefully we will study a dedicated Striver's algorithm one day ! 😁

[@lavanya_m01]

INTUITION: Let nodeA be a parent and nodeB be it's adjacent node. Bridge exists between nodeA and nodeB only if nodeB is not already visited and the lowest time of nodeB (the lowest time gathered among all it's adjacent neighbours) is greater than the time of insertion of nodeA. Hence nodeB cannot reach nodeA. We're checking for a bridge only if nodeB is not already visited because, if it was already visited, the existing edge is like a cycle (i.e another way of reaching nodeB through nodeA) So even if we remove this edge, we can anyway visit nodeB from the path that we came.

[@iamnoob7593]

Hey Striver what a superb video , Came back to revise , Fantastic understood.

[@isheep9025]

alternative method: an edge can be a bridge if and only if its is not a part of a cycle

[@mahasinhossen2502]

this method will take O(e(v+e)) time. you will need O(v+e) time for every edge to check if it is in a cycle.

[@meepo-yk7jc]

I realized that Tarjan's algorithm not only can find the bridges but also Strongly Connected Components(SCC), learn a lot, thanks Striver

[@bhavya8608]

a tough problemmm but you explained it really well!!! Thank you so much!!!

[@raunakkumar6144]

Amazing explanation , cleared my doubt why we are not considering parent edge. Thanks !

[@shubhamgoswami3722]

yes i struggled it too. The main concept behind this algo is , let's say if a parent left its child , and if child don't have access to its ancesstors or grandparents , then the child can't be connected to it's lineage , i.e its a bridge between parent and a child (child don't have any back edge). The second point is why we are not looking for the low time of parent is, if we closely look into dfs , and let's say a parent have many childs but while dry running we choose any one of the child and move forward to do dfs with that choosen child and while again returning we give chance to the other child from the rest ones , so a parent updates it's low if it's any of the child's low is smaller that is if any of it's child is connected to the ancesstors , that means the parent can also access to it's parent via his child. But a child don't update it's low with it's parent's low because in dfs we came to dfs of child and parent is visited and irrespective of whether a parent have access to it's ancesstor or not , but it's already visited so we can't go back to tha parent . :)

[@nealgautam1882]

In the LeetCode problem, it has provided connected graphs as input however, for added functionality for disconnected graphs, the function call for dfs can be done like this: for(int i=0;i

[@muditkhanna8164]

only if the question was named as find the critical connections in all the networks

[@sagarprajapati6026]

yr bhai hard ko itta simple Hats off to you bhai🤗🤗

[@psurya3053]

thank you sir , i understood , after this can you make vedios on further depth topics in graph like flows and cuts etc. your explanation is the best on the youtube. i would like to purchase your courses for competitive programming , if you are teaching.

[@AdityaKumar-be7hx]

Understood! This was the question asked by google when I was in college. Only if this resource was present then :)

[@rushidesai2836]

Which company are u in now?

[@amanxsharma]

u did the best possible to make me understand ..thankyou

[@ganavijayaram7987]

Had to tell this!! First of all thank you very much for all the playlists! Secondly, how can you be soo good at knowing what we understand and we don't. @3:26 timestamp, you just knew that the first timer's might not understand, and you assure we will understand it later. its like 1:1 where we tell we didn't understand, and you say that you'll understand later in the lecture. Damn nice!

[@kartikgarg7541]

Wassup cutie!

[@namangokhru3715]

you are also a good english teacher

[@gauravbanerjee2898]

Crystal clear explanation thanks a lot

[@SaiPhaniRam]

Intuition: Lets say, we need 'x' steps to reach a node 'u'. To mark an edge btw (u, v) as critical, - we should not have any other neighboring nodes to 'v' that can be reached in

[@20je086Saphal]

//to reach the nbr needs for time than node's insertion i.e. only possible when nbr is solely traversed via that node hence it is critical component or a Bridge! if(time[node] < low[nbr]){ bridges.push_back({node,nbr}); }

[@manasranjanmahapatra3729]

Understood. Great explanation for a Hard problem.💯

[@PriyanshuVerma-p9b]

Awesome explanation man ----------Thankyou so much

[@balakrishnanr648]

Us, but indeed a HARD Problem. Like Go through multiple times the video, think a lot internally in the brain. Then Code.

[@mrf92]

amazing striver!! your are a true genius

[@keertilata20]

bhaiya, after the end of the playlist, please provide us a list of all the problems you solved in one place(similar to the sde sheet). It would be a great help when we will do the revision of the graph

[@takeUforward]

It is there on the website

[@keertilata20]

@@takeUforward thank you so much

[@harshalyallewar]

00:04 Bridges in a graph are edges whose removal breaks the graph into two or more components. 02:24 Finding bridges in a graph using Tarjan's algorithm 04:42 Tarjan's algorithm determines bridges in graph 07:07 Determining if a node is a bridge in a graph 09:22 Using Tarjan's Algorithm for bridges in graph 11:36 Identifying bridges in a graph using Tarjan's algorithm 14:01 Understanding the concept of bridges in graphs using Tarjan's Algorithm. 16:10 Finding critical connections in a graph using Tarjan's Algorithm 18:14 Using Tarjan's algorithm to find bridges in a graph 20:20 Tarjan's algorithm identifies bridges in a graph 22:08 Discussing time and space complexity for using Tarjan's Algorithm in graph Crafted by Merlin AI.

[@girikgarg8]

In the else case at line 22, it should be low[node]=min(low[node],tin[it])

[@roushanraj8530]

yes

[@cr7johnChan]

can u please tell me why my code does nt work for larger test cases vectorans; void dfs(int node,int dad,vector&low,vector&visited,vectorgraph[]){ visited[node]=1; low[node]=node; for(int j=0;jlow[node]) { ans.push_back({node,t}); } }else if(low[t]

[@sauravchandra10]

No, it is fine. Watch the explanation again

[@ashwinashok1361]

Nice explanation!

[@r_uhi05]

Great explanation to such a hard prob. Understood!

[@vcs649]

Awesome explanation and presentation as well

[@worldfromhome4033]

Took me watch the video 2 times to understand but yeah understood!

[@UECAshutoshKumar]

Thank you sir 🙏

[@pulkitjain5159]

Comments Padke and Video dekh ke I felt thoda lost , doosri teesri baar dekhne pe thoda anaolgy se samjhne ka try kiya then samajh aya thoda kya hora hai. theek toh m thoda samjhane ka try karta hu , suppose 1.) TIN[ node ] is ki mujhe is node tak aane m kitna time laga , 2.) LOW[ node ] tells ki mujhe is node pe aane pe minimum kitna time laga. ab ise dekho , suppose m parent pe khada hu aur m child pe gaya tha -> when we got a bridge :-> parent -> dekh child mujhe khud tak aane m TIN [ parent ] = 8 sec(suppose) lage hai toh m tujh tak toh 9th second m pahuch jaunga child -> yaar parent 🥲, mujhtak toh minimum aane m hi LOW[ child ] = 10 sec lag jayenge , kaha se ayega tu mujhtak TIN[ parent ] < low [ child ]. hence we got a bridge. when not a bridge :-> parent -> dekh child mujhe khud tak aane m TIN [ parent ] = 8(suppose) sec lage hai toh m tujh tak toh 9th second m pahuch jaunga child -> are parent mein toh khud par LOW[ child ] = 6 sec m hi pahuch jaunga , tu esa kar mere saath aja , jaldi pahuch jayega LOW [ parent ] = LOW [ child ]. let's write a pseudo code using this analogy dfs( node , parent , timer ){ visited [ node ] = true; // mark myself visited tin [ node ] = low [ node ] = timer; // noting the time at which i came on this node timer++; // increase the timer // get all neighbours for( nbr : adj [ node ] ){ if(nbr == parent ) continue; // leave it if(visited [ nbr ] == true ) { // lol , phele se hi visited hai definetly kisi aur raste se aya hoga isliye visited hogya // sirf low ki baat cheet kar sakta yani mein low [ node ] = min( low [ node ] , low [ nbr ] ); }else{ // visited nahi hai , yani yaha m parent child wali baate kar sakta hu , child mera nbr ban jayega , parent meri node dfs( nbr , node , timer + 1) // now , parent bolta , mujhtak aane ka time TIN , tu tera minimum bata // mereko minimu hi LOW[ nbr ] time lagra 🥲, tujhe toh aur time lag jayega if( low [ nbr ] > tin [ node ] ){ // found potential bridge } // mereko minimum LOW[ nbr ] time lagra , aur yeh tujhtak ( parent ) pahuchne ke time se better hai , ise badiya tu mere through aja else{ low [ node ] = min( low [ node ] , low [ nbr ]); } }

[@pulkitjain5159]

samakj ni aaye toh ek baar is analogy se dry run karlena , ajaye toh badiya

[@Aman-dl6cf]

BEST COMMENT EVER , 🔥🔥🔥🔥

[@Aman-dl6cf]

THNX

[@16avikasgupta70]

My bro got some different level of energy

[@SeloniSinha]

Understood sir!!! Such an awesome explanation!!! Loads of thanks sir😄

[@mriduljain6809]

Understood!! Explanation was very clear :))

[@cinime]

Understood! So amazing explanation as always, thank you very much!!

[@roniljain1774]

I wish I could talk to my code the way you do ❤

[@googleit2490]

Understood :) Sep'5, 2023 07:27 pm Pretty much complex

[@taruchitgoyal3735]

Great explanation. Thank you

[@chiranjiveethakur9889]

Very nice explanation!

[@reshusingh3558]

understood sir thankyou for your teaching

[@youracademicfriend-shashwa1051]

Thankyou!! Nice explanation

[@b01adarshrakshit79]

brute force remove each edge and check the number of components if its greater than 1 return edge;

[@aadityavaid6818]

getting a TLE in a testcase having n=1000 and a very large number of connections

[@parshchoradia9909]

Understood SIr!

[@shivkrishnajaiswal8394]

Good explanation.

[@udaypratapsingh8923]

understooood 🐼

[@mahtoji8935]

If anyone of you is having dought that why this condition is being writter low[node]= min(low[node], disc[neighbour]) instead of writing low[node]= min(low[node], disc[neighbour]) this then please jenny mam lecture on this topic . I am sure that all your doughts will be cleared

[@hrishikeshbakshi8961]

This was difficult! But Understood!

[@abhirupadhikary4274]

For condition of critical edge why do we check lowest_time[recently popped node] > time[current node] and not lowest_time[current node]?

[@thaman701]

same query did u get the answer??

[@abhirupadhikary4274]

@@thaman701 Nope

[@thaman701]

@@abhirupadhikary4274 😆😆😆shi h.bhai

[@Hemus212]

understood !! beautiful explanation

[@manojnavinjamuri5867]

lil complex but will watch thrice

[@deepak_joshi_the_conqurer_]

Thank you striver sir!!

[@GANESHSINGH-uc1gk]

dayummm....amazing explanation!!!!!!!!!

[@samarthdengre9706]

Please add a video for Kuhn's algorithm

[@tkr483]

You're realy great ❤

[@VarunSharma-xd8xd]

great explanation

[@nirbhay0799]

Awesome striver👏

[@ateasejee1662]

why we cannot compare low[node] < low[it] instead of tin[node] < low[it] for finding a bridge ?? can anyone give an example ?

[@amritanshu1402]

Loved the way you explained such a hard concept in the easiest manner! Thanks a lot. Guys the least we can do is to smash the subscribe and the like button :)

[@TranTrungKien-us1lu]

can we call "TUF" is "The University Free" ?

[@tanmaybro3812]

7:50 is the crux of whole video

[@varunakrishnani7688]

Understood! :) Thank you! 😊

[@riyarsharma4667]

Understood striver😇

[@rishabhgupta9846]

understood,great explanation

[@sakshamgangwar8271]

But "10" is already visited so as he said later in the video that visited child can't be bridge so i don't understand can anyone tell me

[@subhradippalit5757]

Didnt understood the if condition ,where we are collecting the bridges. why are we taking low[it]>tin[node] ?

[@takeUforward]

If the adjacent nodes lowest time is smaller or equal to current node, so it can reach again via some path, so if its greater, it cannot!

[@subhradippalit5757]

@@takeUforward okay got it , Thanks !

[@cr7johnChan]

@@takeUforward can u please tell me why my code does nt work for larger test cases vectorans; void dfs(int node,int dad,vector&low,vector&visited,vectorgraph[]){ visited[node]=1; low[node]=node; for(int j=0;jlow[node]) { ans.push_back({node,t}); } }else if(low[t]

[@anishraj66]

@@cr7johnChan i have also same doubt bro u check your if condition if(low[t]>low[node]) i think this also should work but dont know why its not working

[@mayankjain-901]

Can't we only use minTime to compare and find the edge is bridge or not , like minTime[node] < minTime[child] , then it is a bridge ,assuming minTime will also be equal of nodes that have a edge and it is not a bridge ?

[@margapuriamukthasrimalyada359]

for input connections as 1 2 3 4 4 7 7 8 8 5 4 5 will it work?? i think we sluld add one more for loop in main??

[@honestad3558]

i got it wow explanation

[@phoenix_1_3]

for directed graphs, we have kosaraju algo. for undirected graphs, there is tarjan's algo. right??

[@GauravJain-zo8gt]

anant jai jinendra sir

[@gsmdfaheem]

Is this new leetcode UI available to everyone?? because mine is still normal and this one looks super cool! Btw awesome explanation..Crystal clear

[@avnish664]

ya

[@sivakumar-wr1hn]

Just wondering if we find node with only one incoming edge and its parent would be the part of result.

[@valarmorghulis9244]

why did you take the timer as global variable. Cant we pass it from main?

[@GAURAVSINGH-t9p]

Why do we need tin array, why cant we just solve it using low array, cant we just change if (low[it] > tin[node]) { bridges.push_back({it, node}); } to if (low[it] > low[node]) { bridges.push_back({it, node}); } Where does it fails, i tried finding the counter example but wasn't able to

[@namanagarwalla1305]

Hey striver you can try explaining in hindi...sometimes explaination becomes hazy when you try in english such as this problem

[@AyushGupta-ux4gq]

class Solution { public: int timer=1; void dfs(int ind,int parent,vector adj[],vector &low,vector &time,vector &visited,vector &ans) { visited[ind]=1; low[ind]=time[ind]=timer; ++timer; for(auto it:adj[ind]) { if(it==parent) continue; if(visited[it]!=1) { dfs(it,ind,adj,low,time,visited,ans); low[ind]=min(low[ind],low[it]); if(low[it]>time[ind]) { ans.push_back({it,ind}); } } else { low[ind]=min(low[ind],low[it]); } } } vector criticalConnections(int n, vector& connections) { vector visited(n,0); vector ans; vector low(n),time(n); vector adj[n]; for(int i=0;i

[@gangsta_coder_12]

Understood 🔥🔥

[@divyarana5486]

This algorithm is for directed graphs, how have you assumed an undirected graph?

[@tanujaSangwan]

Tarjan algo is used in directed graphs to find the scc. But for bridges, it is applied to undirected graphs. In directed graphs, edges have a direction. The concept of a "bridge" in a directed graph is more complex because the directionality of edges influences connectivity differently.

[@anishraj66]

to check for bridge cant we use if(low[node]!=low[child]){ then there is bridge} cant we use this?

[@shivank630]

Why it is not working for finding the number of connected components as the number of connected components should be number of bridges+1 Can anyone tell me the reason..

[@RituSingh-ne1mk]

Understood!

[@googleit2490]

Why can't I just check indegree vector, if it has only one component means it has to be bridge Edit: Got the mistake...

[@amittiwari360]

why low[it]>tin[s] , and not low[it]>low[s] , please tell me because when i did this 15/17 test case pass , i am not able to make that graph condition where this is failing , please help me striver.

[@umeshhbhat]

I had the same doubt, did you find the answer for this?