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.
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.....
@@Samuel_above_fake 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?....
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!!
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!
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.
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.
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. :)
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.
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!
@@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! 🙌🙌
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?
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.
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?
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
---------------------------------------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!
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
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?
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.
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?
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.
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?
--------------------------------------- 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.
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?
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?
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.
--------------------------------------- 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.
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
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.
Even my grandma would understand this topic with your explanation
lmao sir yea his explanation is so clear
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.....
@@Samuel_above_fake 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?....
@@saikarthik559 😂 I do fast typing, is there any problem for you???
@@Samuel_above_fake that'll better help you in competitive programming... not commenting vague here. ☮
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!!
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!
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.
Hats off to you ...
Really great explanation.
Appreciate your hardwork.
You and Ravindra Ravula sir are shaping many computer Engineers in our country 🇮🇳.
Clear, concise, and straight to the point. Thank you very much sir!
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.
Finally a great explanation, not those freaking recursive formulas
When an eight minute RUclips video is better than a whole lecture on the subject.
Sir thank u so much for this video ......I searched at many places .....but u r crystal clear and at the point.....
really appreciate your efforts to explain things so lucidly!
best explanation, algorithms are really hard but with your explanation who will not understand, thank you
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks man, thanks alot
May GOD protect u and guide u❤️❤️❤️❤️❤️❤️
I was soo confused about this topic but your explanation is amazing Sir. Thanks a lot
Dear Abdul Bari, thanks to you I like the algorithms! Thanks so much!
Classic explanation, hats off to you
Ur unbelievable sir!!
Thanks again... ❤️❤️❤️🌹🌹🌹🌹🌹🌹🌹🌹🌹
Simple ,clean ,neat .
Thanks a lot 😊 sir ...
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.
:)
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!!
our faculty copies from you😂😂😂
Teacher ho toh Abdul sir jesa vrna na ho :)
Thank you very much, sir, your explanation about all the topics is very simple and understandable.
Wow, great explanation, really helpful! thank you!
abdul bhai ki jai ho. shukriya bhai......(x100)
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.
Best explanation possible for this algorithm
Exam today, this saved me
Really good explanation, thank you.
Awesome! Thank you, Sir! :)
Really good lecture for free, thank you sir.
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?🙏
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!
@@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! 🙌🙌
@@raywang999 where you understood it so deep any source?
@@raywang999 Thank you SO much!!!
Could you please write this explanation? It will be helpful for me.
Tnx@@satishchandra6623
Alhamdulillah, Very nice exxplanation
🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌THE GOD MR ABDUL BARI 🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌
Keep it going... Your explanation is awesome
This is a very good explanation, thank you.
A very clear explanation sir.
thanks a lot.
a goldmine in youtube
Thank you sir, very clear explanation🥰🥰
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?
Back tracking is only allowed once in finding articulation point.
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?
Excellent explanation, props to you, sir!
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.
what a concise explanation
Finally I get it, thanks man.
How has the formula been derived?
Tarjan's Algorithm
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?
d[3] is 3..not 1
3:59 low value
5:17 find out articulation point
Tnq Soo much sir for u r valuable explanation.
thanks for this explanation
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
---------------------------------------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!
Wow, simply amazing !!
Best explanation.
Awesome explaination sir
Sir , best explanation
This is a great video.
This explanation is 🔥..by the way that formula is derived from tarjan algorithm right?....
Thank you for your efforts
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
very clear explanation, thank you so much!!
soothu
Great! Really helpful! Thank you very much!
in finding the least path L can we assume the path as 5->3->2->1 as it is a undirected graph?
Find lest path in spanning tree
you can't do that, d[3]
Thank you! That was super helpful
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?
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.
jaii Bari sirrrrrrrrrrrrr💥
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?
the formula isn't valid for root node (node from which we started the dfs).
Exception in the root node
Great explanation looking toward more videos about data structures
Semma sir.continue
I watch his videos as brahmastra, when I didnt understood concept reading everywhere😅
What would be the time complexity of this approach? Is it O(V*E)?
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/
how this algorithm will work for undirected linear graph (i.e. no cycle) ?
In that graph all of the vertices are articulation points exept the ones at the bottom of the dfs tree
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
@@abdul_bari THX=)
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.
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?
@@abdul_bari Thank you very much!! You are the best
--------------------------------------- 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.
@@satishchandramedi9729 Thanks for the reply! I already passed the exams though. It was hard but this channel basically helped me a lot!
@@PBNinja That's great! But it might help you during campus recruitment hiring questions!
thankyou sir
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?
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?
What about vertex 6? There is no child of 6.
Thankyou sir... 🙂
Great Explanation, Can you please make a video on Critical Connection in Networks Leetcode 1192
Sir what happens if the graph has only one back edge ?
will the values of L of those corresponding vertices be 0 ?
is the lowest number the lowest vertex value or the lowest discovery time?
Super understandable !
sir please upload videos for decrease and conquer, transform and conquer
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)?
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
We can only go down on the tree, and ONCE we can go on a back-edge.
Sir what if back edge is not present for last number in spanning tree?what is lowest discovery number
By seeing your demonstration style i just want to buy your complete course.
Is there any coupon available please .
Vishal there no other course on algorithms
For 5 and 6
Why cant we go from 3 to 2 and then 1
Like 5->6->3->2->1
what if there's no back edge from a vertex?
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.
Thank you ^^
Thank you.
Sir this game aid i don't like it's does not touch supermacy of this channel it's really precious no need such
Wont 2 will be visited first as it come first in lexical order
Why is vertex 1 not considered an articulation point since the low(4) = 1 and the num(1) = 1 -> 1>=1 ???
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
We can only go down on the tree, and ONCE we can go on a back-edge.
one piece mentioned
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.
@@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
Okay sir got it. Thank you :)
--------------------------------------- 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.