Articulation Points Graph Algorithm

[@aaronlamoreaux5854]

Thank you for this video and all your other videos! I really appreciate all the effort you put into your videos. They are incredibly useful. I hope you never stop making them.

[@tongzhang3474]

line 84 and 85 lowTime.compute(vertex, (currentVertex, time) -> Math.min(time, visitedTime.get(adj)) why do we compare current lowTime with adj's visitedTime, instead of adj's lowTime, if adj is visited? Thank you.

[@ShekharPrasadRajak]

While DFS (say for non root node u), when we came across the visited node (say v) then it should be low[u] = min of node low value (low[u] )and visitedTime[v]. That means there is back edge from node u to v and all the ancestors of u should have low value as visitedTime[v] (until those ancestors are visited after the node u).

[@PabloRausch]

This video is great. I've been struggling to understand this algo for hours before this video

[@SriramNagaraj]

For D to be recognized as articulation point, it doesn't have to wait till it visits both C and E. It becomes a articulation point when the control is returned from C to D.

[@ankitkushwaha633]

what if we don't have e

[@mihaidogaru9938]

Polytechnic University of Bucharest, Automatica si Calculatoare, thumbs up!

[@venupriyasivaraman1962]

Hi, thanks a lot for your videos. I have referred your videos for my exams and i scored good marks. Thanks again

[@arungopalan]

I think there is a small mistake. The low timer of F is 7 (because of H) and low time of E is then 7 (because of F). However this does not change the list of articulation points you arrive at.

[@limychelseafc]

but we are always taking the minimum of the two right, so we dont update if 7 > 4??

[@nisharege857]

superb explanation!!! thank you very much!

[@madhavgaba7617]

Looks like some issue in the condition-2: Visited time

[@mohammedalhanooti3967]

this is the best explanation of the problem

[@22PARTHGUPTA18]

Please post similar explanatory video for finding bridges in an undirected graph.

[@sidrajpal9]

Thank you so much, the example you took explained the concept beautifully.

[@GauthamBangalore]

Thanks for the video. Very nicely explained.

[@supreethbaliga7353]

Hey. I appreciate these videos a lot. They really help me understand complex problems and algorithms.

[@akshayavenkatesan2912]

You are the best! Don't stop making these videos!!

[@idiot7leon]

Here are my newbie questions: 1. why does D have only 1 child? Why is E NOT counted as the child of D? 2. how to save/keep the relationship of parent-children? 3. how is B's low time updated with "minimum of whatever the current low time is", programmtically? 4. why is H's lowest time NOT updated with F's? Under what condition should one's lowest time be updated? With what? (It looks like the lowest time/value among itself and both/all of connected points). 5. how is backtrack retrieved/performed? D -> C -> A -> B (backtrack starts) -> A -> C I will come up with my solutions if understanding them.

[@idiot7leon]

Answers: 1. around 9:03, E is counted as the other child of D. So D has 2 children.

[@idiot7leon]

A few tutorials that help me understand those newbie problems better: kzbin.info/www/bejne/iqq6pattppd3bbs&feature=emb_logo kzbin.info/www/bejne/l4u7mmSro6eXgKM

[@GauravGupta-zw7hz]

Thanks a lot for making this video with simple explanation.

[@shahriyarnovruzov2986]

great explanation, thank you very much Tushar Roy, great job :)

[@kanimozhikalaichelvan6927]

Excellent Explanation. Thanks a lot :-)

[@pallavivenkatesh8319]

very nice and interesting videos...was actually looking for an algorithm to find articulation points in a graph....quite helpful...can u plz tell me any other algorithm for the same...i need to compare and bring the statistics

[@groovymav1038]

Can we say that the nodes with same low time belong in a cycle? eg A,B,C have same low time; E,F,G have same low time. Is this assumption correct??

[@jdragon8184]

yeah kosaraju algo does it for me otherwise if we have multimap to store and update the low times we can easily call them when needed but it will take too much time

[@cashflow9156]

At 19:35, vertex C is in the visited set, so why does the code go into the if statement and not the else statement?

[@Klaster961]

Nice video, thanks But there is an error, A's low time should not be updated from 2->1, because min(lowTime(a), visitedTime(b)) = 2. So it should stay 2

[@SonuSonu-tk5pk]

minimum of 2 and 1 is 1 u should compare with the low time of B which is 1

[@hamedo.khaled4824]

In A->B->C graph . why aren't A and C articulation points although removal any of them will result increasing in number of connected components ?

[@svanegasgil]

No, their removal won't result in increasing the number of connected components. If you got: A -- B -- C and you remove A, the resulting graph will have 2 connected nodes: B -- C then, neither A nor C are articulation points.

[@hamedo.khaled4824]

got it..thx

[@kunjalrupala7753]

Why do we update the low time of 'B' as 1 and not as 2 (time taken by C+1 i.e., the time taken to reach it)?

[@jaydeepdugar5612]

would u put a video regarding the proof of this algorithm as in how does this algo works ?

[@thealgorists60]

It is explained here: www.thealgorists.com/Algo/Graph/ArticulationPoint

[@vipulsharma1897]

sir in the code you are just checking for the number of children for a root node.if it's value is greater than 2,it is an attriculation point.but what if the two children are connected?it isn't an articulation point then?is it?

[@sudhanshumongamonga3031]

he said independent, had they been connected the counter of the child count wouldn't increase in the first place because it would haven't gone into the second condition where the child counter is incremented.

[@kaustubhkislay3126]

if the children are connected as was in the example(B & C) , children would remain 1 because C will be discovered by B (not by A) and thus it remains to be 1 and hence its not an articulation point.

[@ikrambk5848]

Excellent explanation (y) big thank you

[@hemantsuthar20]

superb explanation

[@starc701]

why H is not a articulation point, if we remove H the graph will get disconnected

[@Sarthakz99]

what if there is a cycle, then root won't be an articulation point even after having >2 children.

[@shobhitsrivastava4496]

thank you for the video!

[@YogeshPersonalChannel]

Which software do you use for screen recording?

[@snilmayya]

Thank you

[@PranayKumarAggarwal]

Thank you very much :) .. I could never understand this algo before your tutorial..

[@anilkatakam2738]

Code Explanation is too good.

[@SonuSonu-tk5pk]

Amazing and clear Explanation.. Great .. Thanks for the code..

[@neerpatel4647]

It will be good if you rename this video as Tarjan's algorithm... cos other videos comes first when we look for Tarjan's algo,,,

[@priyankarrajgupta4198]

Thanks for your hard work :)

[@cashflow9156]

At 19:30 when you say to go back into the recursion, what part of the code does that? I've tried it and my code ends at vertex D without going back again.

[@cashflow9156]

nvm it was due to the fact that i was returning too early

[@iam_kundan]

Great Video !!

[@ranvijaysingh4400]

Why did you go back to E from F not to G ?

[@dharmendrabhojwani]

v1 -- > v2 --> v3 ? what about this situation. I see that v1 is becoming AP which is wrong. Please explain

[@dharmendrabhojwani]

+Dharmendra Bhojwani thanks Tushar

[@visheshsrivastav2107]

Thanks.It was a brilliant explanation

[@vducky0110]

This algorithm takes some time to sink in for me.

[@devanshbhatia6951]

+1

[@harshitagarwal5188]

as u told atleast one of the 2 conditions be satisfied must be satisfied for a point to be an articulation point, but i could not think of a case when for a point P condition 2 is not satisfied but condition 1 is, ( which makes P an articulation point ). does such a case exists ? moreover if i run that algo. for the case in the figure postimg.org/image/kn02fzdgh/ i would get the answer as 1 (because vertex B have 2 independent child ) although the answer is 0. please tell me where i am going wrong

[@tempregex8520]

@tushar why is the vertex H not in the visited set?

[@sumatraroast1513]

Thanks!

[@swapnilnathgosavi7663]

Nice video sir

[@abhinavgupta6438]

what is the intution behind this low time logic ?

[@SnoozeDog]

Why isn't C's low change to 0?

[@cantwaittowatch]

Tushar - After following your approach and seeing the video clip in here - kzbin.info/www/bejne/goTUk5ScpbaUaZo, I think the following clip is easier to understand, of course they need to be traced to understand well. Just sharing my observation and no means to undermine - Thanks again for sharing your knowledge.

[@quantlfc]

Boss thanks a ton

[@Abhishek-nn2qw]

EDIT: I got it now :D kzbin.info/www/bejne/aJy1dnyhe56Id9U at this point in else condition why you have considered the visited time of A why not its low time? I was solving a problem and was getting WA when using low time but when I changed this to visited time it got AC. But I am not able to understand why that is wrong. If we consider the low time of A instead of visited time then what is wrong with this. Please explain .

[@newworldorder25]

Nice

[@ajr1791ze]

why we didn't unpdate low time for c as 0 .

[@ajr1791ze]

ok , we don't update low for parent node

[@prateeprajput8407]

can u help me for understanding code for dijkstra

[@kartikayy]

How to check two independent children of a parent?

[@iAdrianT]

1 year later: if they dont have an edge connecting them, in the video, nothing connects C and E

[@ashketchum7768]

I think you are wrong. In the above graph, of course, they are independent. But, sometimes, even if there is no edge connecting those two, they may not be independent because of an edge between their children at any depth (also note that these children need not be at same depth).

[@satyadevchandak3783]

sir was really a nice video. got the algo clearly :)

[@swadhindas5853]

Your video is very good but the problem is in the written statements floating on screen.For this a part of the main video can't seen

[@ShubhamGupta-fm7lv]

Swadhin Das you can turn it off by switching off the captions

[@swadhindas5853]

Shubham Gupta how sir

[@물리화학]

좋은설명 ㅎㅎ 코드가 C엿으면 더좋앗을텐데 아쉽지만

[@vivekntl]

Whats with the accent🤔

[@mondal1839]

Unpleasant voice! Though the video is informative.

[@shubhamkumar-hx1fb]

Why do you sfeak and not speak 😂😂

[@experimantalboye8711]

fack english acsense

[@mahbuburrahmanmukdha1002]

I was searching for this this topic and found this. This doesn't make sense. The video is good but it could a little more interesting and the writing could be a little bigger so that all the written things can be seen. Its hard to see all that writings in the white board.

[@SonuSonu-tk5pk]

itne me itna hi milega