5.2 Articulation Point and Biconnected Components

Articulation point is a vertex in a graph, if it is removed, graph will split into components.
PATREON : www.patreon.com/bePatron?u=20...
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...

[@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. ☮

[@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.

[@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!!

[@mateusogawa6617]

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!

[@hardikvansia3293]

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

[@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.

[@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. :)

[@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!!

[@Monica-cq2hr]

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

[@sahithmylavarapu9375]

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

[@amitmagar1675]

really appreciate your efforts to explain things so lucidly!

[@pmoieni]

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

[@miruvarshinifam5955]

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

[@rushikothari1261]

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

[@allawhussein]

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

[@determinator4491]

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?

[@abi6ail]

Wow, great explanation, really helpful! thank you!

[@arnavattri5047]

Awesome! Thank you, Sir! :)

[@martonnemeth236]

Really good explanation, thank you.

[@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!!!

[@amrhamcho1853]

Excellent explanation, props to you, sir!

[@ravipatel3624]

Classic explanation, hats off to you

[@gulfilizisk1543]

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

[@807johnny807]

Finally a great explanation, not those freaking recursive formulas

[@romanarahman5980]

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

[@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.

[@suvijaashri4625]

A very clear explanation sir. thanks a lot.

[@Akashash992]

Keep it going... Your explanation is awesome

[@287MdSahil]

Best explanation possible for this algorithm

[@travisblack9519]

This is a very good explanation, thank you.

[@stith_pragya]

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

[@barabenkag221]

Great! Really helpful! Thank you very much!

[@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)?

[@rohes8129]

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

[@mgphyothant]

Really good lecture for free, thank you sir.

[@Tehbert321]

Thank you! That was super helpful

[@rohes8129]

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

[@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!

[@karnansooriyakumar8002]

Thank you sir, very clear explanation🥰🥰

[@nigamsn748]

Beautifully explained

[@tanisharastogi6575]

How has the formula been derived?

[@0anant0]

Tarjan's Algorithm

[@spotlight4091]

Semma sir.continue

[@swaroopajalasuthram2535]

Tnq Soo much sir for u r valuable explanation.

[@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?

[@sainaveen5659]

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

[@himanshusrihsk4302]

Awesome explaination sir

[@pratyushsrivastava3783]

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

[@ankitraina4047]

Teacher ho toh Abdul sir jesa vrna na ho :)

[@taivinh1986]

what a concise explanation

[@mohammedadel8948]

Thank you for your efforts

[@vbansal345]

Sir , best explanation

[@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?

[@s9chroma210]

Exam today, this saved me

[@notanonymous3976]

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

[@ShaliniNegi24]

Wow, simply amazing !!

[@destroyer_x9595]

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

[@herumuharman6305]

Finally I get it, thanks man.

[@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.

[@shahrahul5872]

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

[@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

[@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?

[@afreedmohmmad]

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

[@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

[@liangtang2127]

very clear explanation, thank you so much!!

[@semmathisaravanamuthu7733]

soothu

[@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]

[@sat3287]

Best explanation.

[@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/

[@shahidsiddiqui6013]

Super understandable !

[@mrudhul145]

This is a great video.

[@ashb8552]

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

[@mohammedabdulazeem5656]

Alhamdulillah, Very nice exxplanation

[@ngn_two6001]

Great explanation looking toward more videos about data structures

[@sachidrolia9628]

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

[@user-um8ps3tl7h]

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

[@toyintoy]

and for a non bicconected graph?

[@starc701]

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

[@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.

[@winner9861]

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

[@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

[@amalmathew5500]

nice video thanks

[@AnitShrestha]

Thank you.

[@SRNR_PODCAST.]

a goldmine in youtube

[@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.

[@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

[@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!

[@jananiselvaraj6180]

Does articulation point and biconnected components mean the same ?

[@rohitkumar-rq6qh]

Thankyou.

[@sindhuramesh3]

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

[@pascalsolutions6158]

Good job

[@HANUMESHMENGCS]

sir can plz take session about strongly connected complet.

[@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

[@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.

[@georgejoseph2553]

Thankyou sir... 🙂

[@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.

[@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.

[@kanarambhari108]

well explation ,thankyou.

[@RORAVIKUMART]

What if there in no back edges??

[@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.

[@anybody_y]

can we arbitrarily choose any vertex as the root for our DFS?

[@anybody_y]

@@abdul_bari thanks!