Tarjans strongly connected components algorithm
ฝัง
- เผยแพร่เมื่อ 20 ต.ค. 2024
- This lecture explains the Tarjans algorithm for finding the strongly connected components in a graph.The previous video explained the same using kosaraju algorithm and link for that is given below.In the tarjans algorithm, we can find all the strongly connected components in just a single traversal of graph.In this video, I have first explained the concepts required to completely understand the reasons behind each step of tarjan's algorithm and then i have shown the dry run example.I have also shown the reason for using low and disc (discovery) time of nodes and how to calculate it with intuition.At the end of the video, I have shown the CODE walk through of this algorithm.This algorithm makes used of Arrays,Stack and a DFS traversal.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL VIDEOS:-
Kosaraju Algorithm: • Kosaraju Algorithm | S...
At 19:50 , If you are confused why only single back-edge is allowed ?
Ans-> We are allowed to have a single back-edge only for calculating low and disc. However, It will have a cascading effect at the given time. If you carefully run the algorithm as dry run then you will find only 1 head node of SCC and hence, there will be only 1 SCC. I hope you got it :)
After watching the video I also find it really confusing, I am not sure but what I think is that (6 and 2) has a back edge relation where we need to check if 6 is part of earlier SCC and also that we know that it's articulation point too, and if we take (2 and 0), for 2 to be part of that SCC there no need to check for the back edge. SO I think min(low[u], disc[v]) is for back edge and articulation point. Hope I am not wrong. : )
@@Góne-y2s Yes right. For tree edge, it will be low(v)
this Algorithm has much application- one you mentioned is SCC, then Bridge and Articulation Point. Though all three are the same thing. first asks for a number of components, 2nd is for critical edges and 3rd is for articulate points.
@@techdose4u True for tree edges and only while tracking back and popping from stack.
@@Góne-y2s you are going deep 🙏🏼 😅 great
this is, in my opinion, THE MOST COMPREHENSIVE explanation of Tarjan's algorithm on SCC. The video contained a huge amount of information but it was delivered in a way that was very easy to follow.
👍
Outstanding video from tech dose 🔥🔥🔥🔥🔥🔥
Thank you so much for this amazing explanation and readable code. Can't believe this is for free.
Welcome :)
At first sight, the lecture looked lengthy and boring but it turned out to be the most amazing and simplified explanation of Tarjan's.
Thank you for this lecture.
This is so good. Very well explained. This is implementation with understanding and not just memorising an algorithm. I did not understand this in striver's video. I tried hard, but this one, just 1 go, and I could code it. Beautiful!
What a great video. Finally, I am able to understand this concept. I can see the efforts you made. Thank you :)
Thanks :)
2 hrs lage ye video smajhne me but ab Confidence aagya is algo me, thanks bhaiya
Welcome :)
I m regreating why I hadn't come to this channel before, love your explanation. Thanks for helping us🙏
you are literally great, literally whenever I did not understand any concept, and then I see your video then all concepts are clear, Thx for such wonderful videos.
Welcome :)
This is such a great explaination of concepts and the algorithm .The code was so intuitive and beautiful . We are so grateful you made this video . Thank you so much !!♥
Welcome 😀
I have been following your entire graph playlist since 1 week and they have been super useful to me. This one was awesome 👌👌. Keep up the good work 👍💯
Thanks ☺️
Took me a lot of time to understand from other sources, but able to understand in one watch here. Excellent explanation. Very easy to understand call stack and how to deduce this algorithm. Great job, thank you!
Thank you so much for making it so clear. This algorithm appears to be very hard but your hard work and awesomeness are just great enough to defeat that hardness. Keep it up sir.
Thanks :)
Thank you very much for the clear explaination...everything is so clear after this video
One of the best explanation that anyone can provide. OP Surya🔥
Explanation is very nice in the entire youtube, I explored alot, but didn't get this type of explanation. and Finally I understand low, disc why we take that ? , each and every concept. it takes me 2 hrs continuously to understand, in every minute , stopped the video and understand the words more focusly and writing on copy, rather it take me time 2 hr, but understanding the algorithm is more important.
Nobody can explain better than you! Thank you...
Welcome 😁
Awesome. I understand from the first try. I really recommend this channel!
Students of JU are proud of u sir , keep up your work
best explanation of Tarjan's Algorithm . Thank you
Welcome :)
I'm wondering how much efforts u've pushed to make this video. Tysm 🙏🙏🙏
Welcome :)
What a coincidence! This morning I was learning this topic! Many thanks for the video.
Welcome :)
this is the best TH-cam Channel for CS by far, Good Job brother
Tech Dose is God!
So good explaination. Finally understood this algo!.
It's a great video. You explained a very tough concept in such a simple way. Thank You so much Sir.
Welcome :)
Top high quality video about computer science graph theory, others I have looked can't compare with yours.
By watching your video, I can truly understand the content from [Geeks for Geeks] and wiki.
Now I am confident, thank you so much.
Welcome :)
Huge respect for such explanation
Thanks :)
Very detailed explanation,thank you sir🙏
Thanks for all the hard work.
Very Nice Explanaton. Keep making videos
Hats off to you sir ! Mind blowing job with this video 🔥💯👌
The dry run really makes it very clear.
:)
Your videos for graph is awesome.. great job 👏
Thanks :)
Excellent sir..! Thanks a lot..!
Great Explanation sir.
Thanks :)
Kosaraju is much more easier than this to implement , but you have explained this really well, thank you
This one is more effective.
Perfect explanation!!
Thanks :)
Superbly explained.Mind blowing bro ❤️❤️
I found this explanation better than That of William Fiset, that one regarding the use of low vs index
Very well and indepth explanantion
Great explanation
Thanks :)
thankyou so much sir, you nailed it
Welcome 😊
Amazing video, Appreciate the effort
Thanks 😊
At 19:50 why are we allowed only single back-edge?
No, you can take the low value at both the step. He has explained it wrong. In that example, you can clearly go from any vertex to any other vertex. They all will account for 1 SCC. As per his algo you will have 2 SCC which is wrong.
I agree, this implementation of having only one back edge is wrong. We can have multiple backedges. It is quite evident from the given graph example that it's a single SCC. I tried the same graph with Kosaraju that's giving me only one SCC. I tried the same graph on GFS's implementation for Tarjans that's also giving a single SCC.
We are allowed to have a single back-edge only for calculating low and disc. However, It will have a cascading effect at the given time. If you carefully run the algorithm as dry run then you will find only 1 head node of SCC and hence, there will be only 1 SCC. I hope you got it :)
Nice explained 👍👍
Thanks
Great video 😇 really 💞. Thanking you so much sir 😊 to making always very helpful video.
Welcome :)
Was waiting for this. Thanks so much!!
Welcome :)
Tech Dose. what is the significance of FORWARD EDGE in Tarjans algorithm ? I understood the roles played by Tree Edge ( for DFS) / Cross Edge (Ignore) and Back Edge ( update low time based on discovery tiime). And also after back track of tree edge traversal we update low time. Forward edge effectively plays the role of back/cross edge depending on presence/absence of its value in stack ?
At 19:47, explanation is that we cannot min low[u] with low[v], it must be disc[v] since 0 is not directly reachable from 6. But for the given graph, even if we consider low[v] instead of disc[v], answer is there is only 1 strongly connected component isn't it? Will there be any case where taking low[v] for back edge yields wrong result. I couldn't think of any. Please let me know if there is such a graph where it yields wrong result
You are right, using low instead of disc will not yield the wrong result.
I loved how he changes pen colour at 32:40
I have a doubt at 19:50, why are we not allowed to have multiple back edges? The reason provided by @TECH DOSE isn't clear :((
Any help would be appreciated.
Your videos are great, mate!
Great video!, so easily taught!
Thanks
Best explanation
Thanks
@@techdose4u This algorithm will help in solving many questions, thanks for ur effort in explaining it :)
Well explained video!
Thanks
thank you sir. It was helpful
You did not explain what would happen in the case of a forward edge. I think that forward edges will be treated similar to the cross edge in the algorithm implementation. Is that right?
great explaination
Nice video as always. Hope you will do more videos about System Design too in the future.
For all those who are wondering why we used low[u] = min(low[u], disc[v]) for back edge, what I think is that if you look at example given at 18:29 you see that from 6 we have back edge to 2 , so let's say if there was an edge from 6 to 5 then only we could say that 0 is lowest node 6 can visit and the component is connected to other component but here only 2 is lowest node 6 can visit. If we will take more than one back edge may be we would mistakenly take cross edges as back edge also.. For current situation we can only take decision for 2 that it part of our component. May be in future when we explore more nodes 0 also becomes part of our scc. I hope it makes sense !!
Sir, I didn't make the stack. I updated only low value and discovery. After completing the traversal, I made a unordered_map and whose low values are same put them into the same key.
But my answer is wrong. I am not getting what is wrong in this.
Bow down to the master
😂
Ok but I am still unable to process when are we using the 1st formula [min(low(u), low(v)] and when are we using the 2nd formula [min(low[u], disc[v])]
kya bat hai,too good
At 15:43, the example looks like 1 strongly connected component right? Am I correct? As each node can be reached from any other node.
If yes, how can we know? as there are 2 lows (0 and 1) after the algo finishes at 20:29.
(0,0) (1,0) (2,0) (5,0)
(3,1) (4,1) ( 6,1)
This is THE BEST!! Thanks a ton!!!!!!
Welcome :)
@@techdose4u I had one doubt. The diagram at 19:45, how many strongly connected components are there? I think the entire graph is strongly connected. Is that correct? If yes, then while updating node no. 6, why can't the low value be 0? because we can reach 0 from 6 and in some youtube videos they said that the scc nodes will have same low-link value.. please clarify
@@prernasingh564 ohh,,, good question. kaha tk kr chuki be 4 mahine me..
Caught ya!!
@@prernasingh564 reply fast if u get notified for me comment, else u wont be alive if u meet ever again
lol!!
@@prernasingh564 After watching the video I also find it really confusing, I am not sure but what I think is that (6 and 2) has a back edge relation where we need to check if 6 is part of earlier SCC and also that we know that it's articulation point too, and if we take (2 and 0), for 2 to be part of that SCC there no need to check for the back edge. SO I think min(low[u], disc[v]) is for back edge and articulation point. : )
Picture perfect my man
Pure Gold
:)
At 12:00, if I take right edge first and the left edge, then 5->3 would be tree edge and not cross edge as node 3 would not be visited before. Am I wrong?
what happens if your graph has multiple parts that are not connected at all?
At 30:21 the edge from 4 to 6 is said to be cross edge but isn't it forward edge?
Will you please explain why we just check for the discovery value of ancestor and don't consider parent for updating low value of a node?
I think I had explained this in the video. Please rewatch and let us know if you don't get it.
Good description of tarjans algo but I found a little inconsistency. While backtracking why are you waiting to change the Instack to false. I feel like that should be immediately changed to false after we complete exploring and not waiting on finding a SCC. It kind of contradicts what you explained at 12:05.
Initially I thought graph algorithms are really easy. Then I came across Tarjan's algorithm😭
😅
Okay let's assume you are sitting in cluster of people and you are connected anticlockwise. Assign number to each person 1,2,3 since you are in cycle eventually you will meet min number. Now think you have clusters of those cycle
@@abhisheksaraf2616 thanks bhai!! 👌👌
@@abhisheksaraf2616 didn't get!
@@akashkumarbeniwal4875 think about cycle in undirected graph if you try to remove any edges or node will it be more than 2 component ans is no now think about a graph with no cycle
Nice video
Can we solved it using iteration?
Can Someone please explain what is low. Am not able to figure it out and its assignment!!
Quality vid. Thanks
Welcome
Thank you so much sir
Welcome :)
Thank you for the amazing explanation! I wrote and executed the code in GFG and it worked BUT when I wrote low[u] = min(low[u], low[v]) FOR THE BACK EDGE, IT ALSO WORKED! Can you please give one example (not from the video) to help us know why we are using disc instead of low?
Yeah, I had the same doubt.
Sir, I dint understand what was the use of doing min(low[u],disc[v]) for back edge instead of min(low[u],low[v]). Aren't they part of the same component. Won't the final answer be the same regardless. An explanation will be highly appreciated. Thank you.
In case of back edge why are we doing low [u] = min(low[u], dis[v]) and not low [u] = min(low[u], dis[u]) . This was my biggest doubt after seeing articles from different sites. Thanks a lot for addressing this .
I thought you were asking me 😅 Okay you just edited the comment I guess.
appreciate your work!!
Thanks :)
I stupidly started doing this on a bi-directional graph and got freaked out when every edge became a back edge LOL.
For me, when I submitted following condition for back edge on gfg as mentioned in the video :
low[u] = Math.min(low[u],disc[v]);
it did'nt pass all test cases.
low[u] = Math.min(low[u],low[v]);
With this condition it worked perfectly fine.
Amazing explanation! thanks much!
Can you also tell me what setup you are using for making this video ? Which tablet and software you are using for drawing/writing ? I wanna build similar setup for daily day conference videos.
Thank you Bhaiya
Where to practice graph questions from??which is best one??
Leetcode or geeksforgeeks
Please help me in my doubt. If the graph is undirected and we are using tarjan algo to find the discovery time and low time then in that case how can we avoid that the child's low time=parent's time since it is undirected and we can reach the parent from the child node as well
I believe you need to explicitly skip parent edges, i.e. you need extra states to store the parent during traversal and if it’s an edge back to the parent, skip it
Your definition of cross edge is bit different than the actual definition of the cross edge. In your definition, you consider a cross edge from u to v if v is not present in the stack. However, this stack is not the same as the dfs call stack. For eg: take the follow adj list representation of a graph:
1: 2
2: 3, 4
3: 1
4:3
Start dfs from node 1. 1->2, 2->3, 3->1 (back edge), backtrack to 3 , backtrack to 2, 2->4, 4->3 (this should be cross edge, because 3 will not be in dfs call stack, however, it will be in the stack variable that you used in the code. Hence, by your code's definition, this is not a cross edge).
Please, let me know if my understanding is correct or not? I got a bit confused due to this. Thanks.
Ok. I found on wikipedia that we don't remove a vertex from the stack when we backtrack from that node to its parent node. So, although 4->3 is technically a cross edge by original definition, but in this algorithm, we will consider it as a "back edge".
Another confusion that I had was why are we using the disc(v) to update low(u) when there is a back edge from u to v, we can use low(v) as well. Turns out that it does not matter. The result will be the same. However, using using disc(v) is "more" correct in the sense that it disc(v) represents the earliest node reachable from u.
in 12:47 how you gonna know that 0 already present in a stack , we cant access 0 until we pop all elements from stack ?
why for every discovered node, you are checking only for backedge and cross edge, if it is not backedge why it cant be forward edge?
Will the forward edge change anything you your calculation ? Low will still be the same. Only the discovery time for the nodes skipped will be different but it doesn't matter. Dry run this and check.
@@techdose4u yes, right, but how do we check if it is a cross edge or forward edge if not backedge
@@ankithreddyadudodla7673 no need to check forward edge
@@techdose4u yes, I do know, but in general I am asking
@@ankithreddyadudodla7673 tell me a use case for it :)
at 15:17 can anyone show me an example of such graph as the one talked about in the note
At 16:08 why did you go to 5 from 2 and not 3 in DFS traversal?
Can anyone give exmaple where low[u] = min ( low[u], low[v] ) { in back edge case} fails ? 19:50
Please read the pinned comment. Try to dry run. It will work.
low[u]==dis[u] is head node then why low[2]==dis[2] but i t cannot be head node?? at 11:04
According to wiki a strongly connected means Every node can visit every other node which is TRUE for 19:50 graph so the ans should be 1 but according to u it is 2
What is ur definition of strongly connected graph
dint understand y we used to formulas for calculating low[u]
Thanks!
At 15:16, you did not explain why it is cross edge and not a tree edge.
hi a lot of thanks for this video but just a request if you can make this explaination in hindi. I am unable to understand after first 20 mins. Its not language problem but i am getting confused with the confused . Again thanks a lot.
You can slow the video and watch part by part. You will understand. English is anyway essential for IT. So, you need to learn it sooner or later. Better do it now.