5.2 Articulation Point and Biconnected Components

[@rahulvijayaragavan4903]

One of the reasons why i feel youtube is a boon is that it gets us to amazing teachers like you, which otherwise will be rare. I am in my 30s but students in this generations are really blessed. Hope they make use of it.

[@yeyuksel]

Even my grandma would understand this topic with your explanation

[@destinyjames6117]

lmao sir yea his explanation is so clear

[@linuxer463]

By seeing your dp, you may have the age around 25, therefore your grandma age may be around 60-70. So, the people who is having age around this range can't know English, therefore how can you say that your grandma can understand this without knowing English? Don't try to impress or show off here.....

[@saikarthik559]

@@linuxer463 By seeing your long message we can say that you have wasted time by typing comment, therefore Don't try to waste your time again ok?....

[@linuxer463]

@@saikarthik559 😂 I do fast typing, is there any problem for you???

[@m1ckey007]

@@linuxer463 that'll better help you in competitive programming... not commenting vague here. ☮

[@ogawamateus]

Thank you so much! I spent way too long trying to solve this problem for my class and to no avail, but when I watched this video I found the solution right away! Thank you!

[@AltairCrysis]

Wow, this was really clear -- I'd gone through 4 different explanations prior to watching this video, and this is the first time I actually understand what was going on! Great job!!

[@cbbforever]

my lecturer spend tons of time to make a piece of garbage 100 pages' slide and explain this to us using 30 mins and I feel like nothing come in my mind, my time has been stolen. And you, my hero.

[@rushikothari1261]

You and Ravindra Ravula sir are shaping many computer Engineers in our country 🇮🇳.

[@mori1799]

Clear, concise, and straight to the point. Thank you very much sir!

[@hardikvansia3293]

Hats off to you ... Really great explanation. Appreciate your hardwork.

[@807johnny807]

Finally a great explanation, not those freaking recursive formulas

[@jaatharsh]

thanks for making the Video Sir, it was difficult for me to grasp this Algo at first, I watched ur explanation twice to get a better understanding. keep on posting such videos.

[@pmoieni]

best explanation, algorithms are really hard but with your explanation who will not understand, thank you

[@romanarahman5980]

I was soo confused about this topic but your explanation is amazing Sir. Thanks a lot

[@Monica-cq2hr]

Sir thank u so much for this video ......I searched at many places .....but u r crystal clear and at the point.....

[@allawhussein]

When an eight minute KZbin video is better than a whole lecture on the subject.

[@amitmagar1675]

really appreciate your efforts to explain things so lucidly!

[@gulfilizisik]

Dear Abdul Bari, thanks to you I like the algorithms! Thanks so much!

[@rohes8129]

Thanks man, thanks alot May GOD protect u and guide u❤️❤️❤️❤️❤️❤️

[@satishchandra6623]

But why this algorithm works? I mean why there is an articulation point when L(v)>=d[u]? Any explanation for this is highly appreciated?🙏

[@raywang999]

cp-algorithms.com/graph/cutpoints.html I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations: A node is an articulation point if: it's the root and has more than 1 child OR A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back) To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor. More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point. Hope that helped!

[@satishchandra6623]

@@raywang999 Great effort! It's Crystal clear now! Since we have an back edge means that the "Earliest time of child (aka L[v]) is already visited from ancestor, so will not become articulation point" ! Thank You! 🙌🙌

[@MayankSharma-sf3hy]

@@raywang999 where you understood it so deep any source?

[@sohamdas9160]

@@raywang999 Thank you SO much!!!

[@rakibmollik8043]

Could you please write this explanation? It will be helpful for me. Tnx​@@satishchandra6623

[@stith_pragya]

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

[@ankitraina4047]

Teacher ho toh Abdul sir jesa vrna na ho :)

[@mohammad_bilal951]

Dear Abdul Bari Sir Please KEEP UPLOADING more lectures to be honestly your videos make more sense and are very simple please keep up the good work. :)

[@TheWebPotato]

Here, once we have found the articulation point. How do we know from which vertex to vertex do we have to draw an edge so that it is bi-connected? Thanks once again.

[@ravipatel3624]

Classic explanation, hats off to you

[@287MdSahil]

Best explanation possible for this algorithm

[@rohes8129]

Ur unbelievable sir!! Thanks again... ❤️❤️❤️🌹🌹🌹🌹🌹🌹🌹🌹🌹

[@ManikandanM-wz2vb]

Thank u so much sir ,Your videos in algorithms is very helpful to me and it also arouses an interest.Finally ur way of teaching is mesmerising!!

[@sahithmylavarapu9375]

Simple ,clean ,neat . Thanks a lot 😊 sir ...

[@miruvarshinifam5955]

Thank you very much, sir, your explanation about all the topics is very simple and understandable.

[@ilovancristian]

Thank you! Also, I have found something related to the last statement: when is node/point 1 an articulation point (8:05). Maybe it helps somebody. First time this was confusing for me because I thought that if node 1 has more than 1 neighbor then 1 is an articulation point, but that is not true. For instance, if node 1 belongs to a cycle, then he has more than 1 neighbor, therefore he is not an articulation point. However, I found that 1 is an articulation point if he belongs to more than 1 biconex components. That is how I check if 1 is or not an articulation point.

[@s9chroma210]

Exam today, this saved me

[@jknair0]

I didnot understand the lower dfs number was derived. what path is being taken. How are those determined as back edge. I can go from 5 -> 6 -> 3 -> 2 -> 1. Why are we determining 3 is lower dfs number?

[@pavanmandru6481]

Back tracking is only allowed once in finding articulation point.

[@tanisharastogi6575]

How has the formula been derived?

[@0anant0]

Tarjan's Algorithm

[@marykapodistria7204]

How does this work for 3 as the parent and 2 as the child? I mean the formula L[v] >= d[u] where u = 3 and v = 2. L[2] = 1 and d[3] = 3 thus this shows 3 is not an articulation point

[@satishchandramedi9729]

---------------------------------------Credits: Ray Wang------------------------------------------------------- cp-algorithms.com/graph/cutpoints.html I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations: A node is an articulation point if: it's the root and has more than 1 child OR A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back) To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor. More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point. Hope that helped!

[@mgphyothant]

Really good lecture for free, thank you sir.

[@pratyushsrivastava3783]

abdul bhai ki jai ho. shukriya bhai......(x100)

[@abi6ail]

Wow, great explanation, really helpful! thank you!

[@marshallokafor5034]

Dr. Abdul, there seems to be a confusion here Sir. What if we evaluate L[2] and its parent is V(3) which has a D[3] = 1. But V(3) is definitely an articulation point but this scenario i have just mentioned will evaluate to False. Can you clarify Sir?

[@140_kenguvabhavesh]

d[3] is 3..not 1

[@suvijaashri4625]

A very clear explanation sir. thanks a lot.

[@SRNR_PODCAST.]

a goldmine in youtube

[@ayush5234]

Instead of L[v] >= d[u] , i wrote L[v]>=L[u] It passes most of the test cases but obviously some are failing. I am not able to draw any graph for which L[v]>=L[u] produces incorrect result. Can anybody help?

[@ashb8552]

For 5 and 6 Why cant we go from 3 to 2 and then 1 Like 5->6->3->2->1

[@martonnemeth236]

Really good explanation, thank you.

[@Akashash992]

Keep it going... Your explanation is awesome

[@mohammedabdulazeem5656]

Alhamdulillah, Very nice exxplanation

[@nikhilkalyan6273]

in finding the least path L can we assume the path as 5->3->2->1 as it is a undirected graph?

[@neeleshbhajantri6283]

Find lest path in spanning tree

[@kotzkica]

you can't do that, d[3]

[@shikhavyaghra3347]

Wont 2 will be visited first as it come first in lexical order

[@travisblack9519]

This is a very good explanation, thank you.

[@sachidrolia9628]

sir please upload videos for decrease and conquer, transform and conquer

[@karnansooriyakumar8002]

Thank you sir, very clear explanation🥰🥰

[@sainaveen5659]

This explanation is 🔥..by the way that formula is derived from tarjan algorithm right?....

[@starc701]

🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌THE GOD MR ABDUL BARI 🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌

[@taivinh1986]

what a concise explanation

[@divyanshuyadav4148]

how this algorithm will work for undirected linear graph (i.e. no cycle) ?

[@mikloscsizmadia780]

In that graph all of the vertices are articulation points exept the ones at the bottom of the dfs tree

[@薇季芬]

3:59 low value 5:17 find out articulation point

[@kermi123d]

nice! but why not from 1 first to 2? i learned that its normal to do it in order. so 1-->2-->3-->5-->6-->3-->4-->1

[@kermi123d]

@@abdul_bari THX=)

[@0anant0]

The general algorithm for DFS visit is: while not visited, do DFS visit. So it doesn't matter where you start. You will get a diff DFS tree based on where you start and the order of nodes in the adj list.

[@usamaalioffical]

Sir you are a living legend Your videos are awesome one thing that you should also add code in your videos of algorithms and explain it.Hope you will look into this matter.Lots of love from Pakistan

[@asrithraj1426]

our faculty copies from you😂😂😂

[@arbazshaikh4447]

Great Explanation, Can you please make a video on Critical Connection in Networks Leetcode 1192

[@pjac744]

What would be the time complexity of this approach? Is it O(V*E)?

[@dethswurl117]

The time complexity is the same as DFS which is O(V + E) according to: www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

[@souvik33and37]

thanks for this explanation

[@tadassatafarra7503]

why the L(6), i.e. L of vertex 6 isn't 1? we can use the path 6->3->2->1 and because L(1)=1 we can say that L(6)=L(1)=1

[@mikloscsizmadia780]

We can only go down on the tree, and ONCE we can go on a back-edge.

[@himantabiswadeka6922]

Sir, what if we take an array of size equal to that the number of vertices and insert the total number of incident edges per vertex( like we can calculate the indegree and outdegree of a directed graph), then input the adjacent matrix of the corresponding graph, the vertex having highest number of incident edges will be the articulation point in most cases! Sir, I don't have much knowledge regarding that, just asking can we do that?

[@afreedmohmmad]

Sir what if back edge is not present for last number in spanning tree?what is lowest discovery number

[@PBNinja]

What if the vertex chosen when comparing has no back edge? What would be his Lowest Number? Should it be its discovery time? or the discovery time from its last descendant?

[@PBNinja]

@@abdul_bari Thank you very much!! You are the best

[@satishchandramedi9729]

--------------------------------------- Credits: Ray Wang ------------------------------------------------------- cp-algorithms.com/graph/cutpoints.html I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations: A node is an articulation point if: it's the root and has more than 1 child OR A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back) To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor. More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.

[@PBNinja]

@@satishchandramedi9729 Thanks for the reply! I already passed the exams though. It was hard but this channel basically helped me a lot!

[@satishchandramedi9729]

@@PBNinja That's great! But it might help you during campus recruitment hiring questions!

[@herumuharman6305]

Finally I get it, thanks man.

[@adityawath7646]

I watch his videos as brahmastra, when I didnt understood concept reading everywhere😅

[@bushidocodes]

Can you please clarify how one algorithmically finds the "first backedge"? Based on what you show, where the root vertex resolves to the backedge from vertex 2, it seems like it must be level-synchronized BFS, where we compare all backedges in a given level and resolve to the highest reaching backedge. Is that what you would envision?

[@bushidocodes]

One other thing I've noticed while implementing this is that there might be parts of the spanning tree that don't encounter any backedges when traversing downwards(e.g. 5 if we were to delete the backedge from 6). It seems that we could remove 6 without problem, but removing 5 would make 6 it's own graph. I think the way to get around that is to label vertices at having an L of MAX_INT to make sure the formula finds those as well, but ignore vertices iwth MAX_INT that are also leat nodes on the spanning tree.

[@Sweety51200]

Give an example of a graph which has a cut vertex but does not have bridge ? ...sir

[@swaroopajalasuthram2535]

Tnq Soo much sir for u r valuable explanation.

[@shitposting2234]

one piece mentioned

[@michaeldeguire2410]

Why is vertex 1 not considered an articulation point since the low(4) = 1 and the num(1) = 1 -> 1>=1 ???

[@amrhamcho1853]

Excellent explanation, props to you, sir!

[@nikhilendrarathore3040]

I am a little confused. If we take the parent-child pair of [1,4] then L[4] = 1 = d[1] then L[4] >= d[1]. Does that mean that 1 is also a articulation point?

[@madhukumarganesh4987]

the formula isn't valid for root node (node from which we started the dfs).

[@subashkannan949]

Exception in the root node

[@destroyer_x9595]

Sir what happens if the graph has only one back edge ? will the values of L of those corresponding vertices be 0 ?

[@User-ow7rn]

sir ,at 3:33 why 2 is visited at 6th? why not at 2nd?generally in for loop ,we start from 1 to n,so 2 will come first,right?

[@shahrahul5872]

Here there are no directed edges so why lowest for 6 is 3 ,we can still go from 3 to 1 ?

[@ngn_two6001]

Great explanation looking toward more videos about data structures

[@sindhuramesh3]

request you to do some video for Bit manipulations in c++

[@lifeatovarun]

Sir this game aid i don't like it's does not touch supermacy of this channel it's really precious no need such

[@notanonymous3976]

is the lowest number the lowest vertex value or the lowest discovery time?

[@vishalgoyal9180]

By seeing your demonstration style i just want to buy your complete course. Is there any coupon available please .

[@abdul_bari]

Vishal there no other course on algorithms

[@arnavattri5047]

Awesome! Thank you, Sir! :)

[@薇季芬]

關節點會導致 當某個點 崩潰的時候，會導致整個網路分成兩半 從而使系統故障

[@himanshusrihsk4302]

Awesome explaination sir

[@thepinkcodon]

Sir, what do we do if we have to find cut vertices/articulation points bw a unique source and a unique sink in a DAG (Directed Acyclic Graph)?

[@liangtang2127]

very clear explanation, thank you so much!!

[@semmathisaravanamuthu7733]

soothu

[@HANUMESH8]

sir can plz take session about strongly connected complet.

[@sayandey1478]

low [6] can be 1 also, why is it 3? we can go 1 via 3, right? I know it should be 3 but why? what's the definition

[@harshitha.m.4189]

We can only go down on the tree, and ONCE we can go on a back-edge.

[@sat3287]

Best explanation.

[@JoffreyB]

what if there's no back edge from a vertex?

[@jay-rathod-01]

assume there is no 6 vertex so now acc to formula 5>=3 so we still know that the d[3]=3 is still a articulation point. try it.

[@mohankrishna3635]

sir for (1)--->(2) is condition is satisfying but (1) is not a articulation point

[@satishchandramedi9729]

1(root) is default articulation point. So this won't work for root

[@mohammedadel8948]

Thank you for your efforts

[@ShaliniNegi24]

Wow, simply amazing !!

[@jananiselvaraj6180]

Does articulation point and biconnected components mean the same ?

[@vbansal345]

Sir , best explanation

[@winner9861]

sir, is there any getting the chance of 2 or more articulations points in a single graph >>>IF ANYONE KNOW PLEASE TELL ME

[@mrudhul145]

This is a great video.

[@spotlight4091]

Semma sir.continue

[@puspraj4687]

Are articulation point and biconnected components same..??

[@madmax2442]

Articulation points are the vertexes which when deleted from a graph yields two (or bi) connected components. They are not same but the latter is a consequence of removal of former.

[@ajay.chawla]

The back edges how are they used and how to connect them to find L. For one of the question there were only 2 back edges and thus i got L value 1 for all vertices. I didn't understand about L.

[@ajay.chawla]

@@abdul_bari sir suppose if the node is far from a back edge then what to do how to traverse that and get L for it

[@ajay.chawla]

Okay sir got it. Thank you :)

[@satishchandramedi9729]

--------------------------------------- Credits: Ray Wang ------------------------------------------------------- cp-algorithms.com/graph/cutpoints.html I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations: A node is an articulation point if: it's the root and has more than 1 child OR A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back) To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor. More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.