G-55. Bridges in Graph - Using Tarjan's Algorithm of time in and low time
ฝัง
- เผยแพร่เมื่อ 20 ต.ค. 2024
- Leetcode-Problem Link: leetcode.com/p...
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
Had to watch this 3 times to completely understand. Probably the most difficult of the playlist.
haha same. my brain got messed up from this algo
I watched this video. And again cam back to watch this after 4 days. Now i clearly understand whole process!!!!!!!!!!
thanks bro i am leaving this video
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.
I think this problem is very hard to explain. But striver did it very clearly....Awesome!!
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❤
kya bol rhe ho bhaya?
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
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
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.
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.
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
@@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.
@@devanshverma8050 thnxx bhai
Thanks, I learned bridges before from a lengthy video somewhere and your video is a quick review and saves me lots of time.
zabardust bhai, nowhere is it as clearly explained as this. india is really vishav guru - we teach the entire world
It was hard first but then I watched the video twice and now I understand the problem. Striver is amazing!
A visited array is not needed, if tin is initialized with -1, we could check if tin[i] == -1. Btw, an amazing explanation. ❤
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]
@@cr7johnChan your condition low[t] > low[node] is wrong, it should be low[t] > in[node]
hell yeah! Finally completed the series. Thanks a lot Striver!
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
only if the question was named as find the critical connections in all the networks
this is only explanation can be for this tough question on youtube thanks striver !!
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!
Wassup cutie!
Insane stuff . So well explained
Understood, Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Hey Striver what a superb video , Came back to revise , Fantastic understood.
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
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.
a tough problemmm but you explained it really well!!! Thank you so much!!!
God!! How could you explain it so nicely.... Thank you so much for the explanation
yr bhai hard ko itta simple Hats off to you bhai🤗🤗
alternative method:
an edge can be a bridge if and only if its is not a part of a cycle
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.
Ok got it after watching twice but i guess it will take some time to digest .Thanku Striver Sir
Understood! This was the question asked by google when I was in college. Only if this resource was present then :)
Which company are u in now?
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.
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.
I realized that Tarjan's algorithm not only can find the bridges but also Strongly Connected Components(SCC), learn a lot, thanks Striver
u did the best possible to make me understand ..thankyou
//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});
}
you are also a good english teacher
Understood. Great explanation for a Hard problem.💯
Crystal clear explanation thanks a lot
Awesome explanation man ----------Thankyou so much
Amazing explanation , cleared my doubt why we are not considering parent edge. Thanks !
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 . :)
amazing striver!! your are a true genius
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
It is there on the website
@@takeUforward thank you so much
Great explanation to such a hard prob. Understood!
Understood!! Explanation was very clear :))
Awesome explanation and presentation as well
My bro got some different level of energy
Thank you sir 🙏
Understood sir!!! Such an awesome explanation!!! Loads of thanks sir😄
Understood! So amazing explanation as always, thank you very much!!
In the else case at line 22, it should be low[node]=min(low[node],tin[it])
yes
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]
No, it is fine. Watch the explanation again
Took me watch the video 2 times to understand but yeah understood!
Thankyou!!
Nice explanation
Very nice explanation!
Great explanation. Thank you
For condition of critical edge why do we check lowest_time[recently popped node] > time[current node] and not lowest_time[current node]?
same query did u get the answer??
@@thaman701 Nope
@@abhirupadhikary4274 😆😆😆shi h.bhai
Good explanation.
Us, but indeed a HARD Problem. Like Go through multiple times the video, think a lot internally in the brain. Then Code.
I wish I could talk to my code the way you do ❤
understood sir thankyou for your teaching
great explanation
understood !! beautiful explanation
You're realy great ❤
dayummm....amazing explanation!!!!!!!!!
understooood 🐼
Please add a video for Kuhn's algorithm
This was difficult! But Understood!
Thank you striver sir!!
Understood SIr!
why we cannot compare low[node] < low[it] instead of tin[node] < low[it] for finding a bridge ?? can anyone give an example ?
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 ]);
}
}
samakj ni aaye toh ek baar is analogy se dry run karlena , ajaye toh badiya
BEST COMMENT EVER , 🔥🔥🔥🔥
THNX
Awesome striver👏
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 ?
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.
I had the same doubt, did you find the answer for this?
for directed graphs, we have kosaraju algo. for undirected graphs, there is tarjan's algo. right??
understood,great explanation
Didnt understood the if condition ,where we are collecting the bridges.
why are we taking low[it]>tin[node] ?
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!
@@takeUforward okay got it , Thanks !
@@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]
@@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
why did you take the timer as global variable. Cant we pass it from main?
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
Understood! :)
Thank you! 😊
Understood :)
Sep'5, 2023 07:27 pm
Pretty much complex
Is this new leetcode UI available to everyone?? because mine is still normal and this one looks super cool!
Btw awesome explanation..Crystal clear
ya
getting a TLE in a testcase having n=1000 and a very large number of connections
can we call "TUF" is "The University Free" ?
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
to check for bridge cant we use if(low[node]!=low[child]){ then there is bridge} cant we use this?
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??
This algorithm is for directed graphs, how have you assumed an undirected graph?
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.
Just wondering if we find node with only one incoming edge and its parent would be the part of result.
lil complex but will watch thrice
Understood striver😇
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 :)
brute force
remove each edge and check the number of components if its greater than 1 return edge;
y didnt you check minimum adjacent for node 5
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..
No audio after 0:23?
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
please make playlist on cp
Can this be somehow done with dsu?
Why do we have to declare timer globally? Can anyone explain?
Understood 👍
i got it wow explanation
thanks
Understood ❤
Superb
Understood 🔥🔥
Why can't I just check indegree vector, if it has only one component means it has to be bridge
Edit: Got the mistake...