Initially I thought it was easy, until I figured out the edge case. Probably could have been a cleaner implementation if the camera pressure was not there :P. But this is what time constraint does to you. It was an amazing experience :)
What would the solution be if we change the question to - Find the number of edges to be removed such that the sum of weights of removed edges is minimum?
Nice explanation and I thoroughly enjoyed the problem solving part, one edge case I could think this is missing is the component can have both cyclic part and non cyclic part, so greedily first we have to remove non cyclic edges within a component and then start removing cyclic edges and so on. What do you say?
The given solution misses one edge case, imagine a component with 1 - 2 - 3- 4 - 5 - 3 , in this component we have a cycle, but still if we remove just the 1-2 edge, it will split them into two components. The correct solution seems to be the one where we end up removing the nodes with the smallest degrees, and then keep doing till we get the answer. This might also have some edge cases, need to grill on it. Minimum degree edges which are not a part of cylce, is what we have to grill on, does not seems that easy..
Even this does not work, Consider follwing case n=9 m=12 k=4, 1-2 2-3 3-4 4-1 5-6 5-7 6-7 6-8 6-9 7-8 7-9 8-9 Now, smallest degree is 2 for nodes 1,2,3,4,5 . Now if you select 5 first, then required edges to be removed is 4 but if you select apart from 5, required edges will be 3. So it depends on which node with minimum degree you select
Exactly thought the same, you need something like topological sorting and also keep track of which compos contain cycle, and calculate accordingly, I guess this solution would be a bit more trickier than the one you wrote😜
@takeUforward I think solution would be to find the bridges, each bridge would give you 1 more component(as it's an undirected graph it would be connected), If we fall short, we need to maintain indexed min heap of vertex's as all the components would be cycles and remove vertexes with minimum degrees, update the remaining degrees of adjacent vertexes and repeat till we reach #of Vertexes. (Max number of components in a given graph).
He may not be able to come up with the 100% accepted solution which is probably hard for a problem like this in an interview or in front of a camera but what he said at the end is 100% correct. Interviews are just not about if you were able to solve a probem but how you approach a problem.
What about this solution.... You count the indegree of all nodes. Subtract the 'k' from total components. That becomes your target. Now keep on visiting those nodes which has minimum indegree greedily. Disconnect them and add their indegree to the answer. Visit the immediate neighbors and decrease their indegree by 1. Seems to work on all test cases I came across.
n=8, m=9, k=2 1 2 2 3 3 4 4 1 3 5 5 6 6 7 7 8 8 5 Try on this test case.., you answer would be *2* (minimum indegree is 2 here), but u can just remove the 3-5 edge to make 2 companents. So, actual ans is *1*
@9:39 5-6 6-7 7-8 won't break the component , they are part of the cycle too as 8-5 is. Just find all the cycles in the graph and keep the list of edge not in any cycle. After that you can also find the edges with which you can have your prob solved in minimum cost not just minimum number.
Yes you are correct. That's what I replied. Each edge is dependent whether the other edge has been already removed or not. Even removing 6-7 will not break the component.
@@surajmamgai102anybody please tell me which programming language striver bhai uses to solve the problem in this video..I'm completely new so ...c,c++ or java
my approach: 1). count no. of components - x if x>=k return -1 2). so, we need to make the k-x components 3). calc the degree of all the node and put it into treemap, tm 4). take a variable ans =0 for min #edges need to remove 5). iterate over treemap until x
We can utilize the property of bridges because as per definition "a bridge is an edge which on removal increases the number of connected components by one". The procedure I have thought of is, 1. We have to make k connected components. 2. Let the current number of connected components be 'curr_con', now 'k-curr_con' more components to make. 3. Count the number of bridges available in the graph (using DFS), let it be 'b' and break the bridges, now ' k-curr_con-b' more components to make. 4. Now again find the number of bridges, break them and keep on repeating this until we make it to k connected components.
@@varungurnani4989 It will fail when there is no bridge present at the moment, for eg, a square has no bridge, therefore it will lead to an infinite loop of checking same graph structure again and again.
My approach 1) create an adjacency matrix for all the nodes in the graph using DFS. 2) while DFS, find the total number of islands/components present in the graph by having the visited vector (let us assume total components = x). 3) (k-x) is the required number of extra components. and ans=0. 4) start a loop for (k-x) times. 4) parse the adjacency matrix and find the node that has the lowest degree (least number of adjacent nodes) 5) Add the degree to the ans (this separates this node into a new component) 6) also remove the current node from the adjacent nodes. (updating the adjacency matrix after removing nodes) 7) return the final ans.
@@user-rn1yb5pq8k that would be wrong as you are having a greedy approach. Which would not work for some edge cases. Like Imagine you have 2 big clusters of nodes and they are connected to eachother inside the cluster now also let both of them to be identical and now let a node be added to any one cluster so that it is connected to 3 nodes And now the time is to connect the 2 clusters select 2 nodes from both the clusters except the 3 one that we added.now make the graph a single component by connecting the 2 components that we had originally Now you have a graph So if k=2 All you req is to sever that final edge that you had so your answer should be one But from your algo we should remove the 3 edge node If you are able to understand this case then good .other wise I may answer it in more detail
Lots of respect to Striver writing so much code to guide us through. However suppose the graph initially has only one component which is densely connected with a lot of edges and k=2 that is you have to remove some edges so that you get one more component. In this code first you would end up removing all the edges that are causing cycle in the graph and 1 more edge to make a new component. But it is possible it is not the minimum number of edges required to make 2 components but far more than the actual answer. Am I wrong somewhere?
Asking constraints for n to understand the time complexity and understand which algorithm can be fit there ...is something I loved most ....I never knew this trick can be useful in interview
Adding one more thing ....not giving up and trying to write code even if it is not correct.....In my last interview I had 3 coding questions (1 easy and 2 medium) ..I was able to solve starting two with multiple approach but in last one I was only able to give brute force and better approach and while trying to give optimal solution I gave up ...and guess what ....I gave almost every answer I still got rejected due to giving up attitude....( Lesson learnt but hurtfully)
My Solution can be like finding all bridges in the graph using tarjan's algorithm for undirected graph along with that storing bi-connected components using stack . removing a brigde will surely give you a more connnected component. So Assuming initially there was a single connected component in the graph.If we got n bridges then we can get n+1 components . if n+1>k then we will delete only k-1 brigdes else if(n+1
Very good mock interview, Learned so many things. I have one doubt in your example only. 1) 1 - 2 - 3 - 1 2) 4 - 5 - 6 3) 7 - 8 - 9 - 10 - 7 - 9 k = 8 (You took 7 but I took 8 because i thing here is an edge case). From your code it will be 3 (already given) + 2 (more from 2nd compo) + 1 (cycle removing edge in 1st compo) + 2 (more from 1st original compo) + 2 (cycle removing edge from 3rd compo) + 1 (from 3rd compo) edges req = 3 + 2 + 1 + 3 + 2 + 3 = 11. components = 3 + 2(from 2nd) + 2(from 1st) + 1(from 3rd) = 8. From my code it will be 3 (already given) + 2 (more from 2nd compo) + 2 (cycle removing edges from 3rd compo) + 3 (more from 3rd compo) edges req = 3 + 2 + 2 + 3 = 10. components = 3 + 2 (from 2nd compo) + 3 (from 3rd compo) = 3 + 2 + 3 = 8. At the end , I got Answer with 1 less edge required. So, I think that last greedy approach won't work every time, We need to check that how many requirements of componenets, according to that we need to break cycles and get more components from that component. It means At Last, "The count of cycle breaking edges and getting components from it", this thing should be minimum instead of "only minising the cycle breaking edges". Please check once and correct me if i am wrong. Thanks for Fantastic mock interview.
This was fun to watch xD. I think a more interesting problem would be to find out the minimum weight of the edges to be removed instead of the number of edges. Also, I think there might be a mathematical solution for the "number of edges" problem wherein we look at the number of edges in each component and make some greedy choices.
I think Edmond Karp variation of Ford Fulkerson method to find the maximum flow between source and sink nodes which would be equal to min cut will work. We probably have to do it for all the possible pairs in the graph and then pick the one with minimum cut and then remove the edges from the graph. This will lead to 1 more disconnected component in the graph with removal of minimum cost of edges. Have to do this k - 1 times to have k components. Complexity goes somewhere around k * V2*(V*E2).
Got a Solution -- using concept of degree and min heap Priority Queue note -- maximum disconnected components = n (number of nodes) as constraint is 1 n-1) ; 4 - have a min priority queue storing ( {degree,node} ) ; 5 - push all nodes with their respective degrees ; 6 - pop() current node at each iteration do ct ++ ; ans +=degree[current] and for all neighbouring nodes degree - - ; push them and do this til ct == k 7 - return ans ;
This is the approach i could think of using UNION-FIND:Let me know if I am wrong ^^ We need to find the minimum number of edges that can be removed to get exactly k-connected components. Consider it the reverse way: Find the max number of edges that can be joined to give you exactly k connected components. Inittially consider all the nodes as individual graphs(consider each node as the parent of itself). USE UNION -FIND to join two nodes and check the number of components thus remaining(check number of unique parent nodes- make a parent array corresponding to the ). Keep a count variable to store number of edges covered. There will be a point you reach where there will be exactly k unique parents. Keep going forward but this time only use an edge if on using it, two components of same parent are connected(because cycles won't increase the number of components). Only then increase count. Count will be your answer.
Thanks u striver Bhaiya and keerti didi for making this video this is very helpful and interesting video how to approach problem, represent to our ideas and thought process to interviewer. 😍😍
I think, we can use union find . If both a and b belongs to same parent then breaking a----b edge won't give us new components. This way we can keep track probably.
we can also use Degree of a node in a graph property here . NOTE : Here the cost is the no of edges that should be removed to make a new component Approach :- we know that a node with a degree one can always give us a new component with a cost of 1 . A degree of node 2 give us new component with a cost of 2 and similarly for a component with a degree of n we get a new component with a cost of n . So basically we need to spot the nodes with a degree one in the current formed graph , another thing is that when we remove a node we have to decrease the degree of all the nodes which are directly connected to it by 1 . And then just iterate till the components are not equal to K along with adding the cost Pls comment if there are any edges cases / logic error in the approach
Logic is wrong. If we consider this case when k = 2: 2 4 | \ / | 3 --7-- 6 -- 1 | / \ | 5 8 clearly, your logic would say the answer is 2, but the answer should be 1.
For the correct solution I think initially we should try to remove the bridges as removing one gives one new component guaranteed.Then if we still need more components,we are then left with disconnected graphs in which each one of the nodes obvously belongs to a part of a bigger cycle and there maybe smaller cycles including some subset of nodes in that component also.No idea how to proceed from this...😅
what I have seen in almost other videos of keerti ,It was always like Keerti use to get Upperhand but here it was like Interviewer got nervosed by interviewee and Literally Striver Being Striver You knocked it Bro.Motivates me for Self-learning
I think there is an edge case in 7 - 8 - 9 - 10 - 7 - 9. We can remove 7-8 and then 8-9 then we have 1 more component = 8. So we don't really need to remove 2 edges to get one more component. Instead I would find the bridges. If a + bridges >= k thats a return. Else keep track of the sizes of cycles like in this case 3, 3. Then individually check for those cyclic components
Can someone please comment on below algorithm that I thought: 1) find no. of connected components. Let it be x. 2) find degrees of each vertices and store it in hashmap. also create a treemap. 3) remove any smallest degree vertex from treemap (that is why I took treemap to easily remove vertex with smallest degree). Lets say vertex v has smallest degree d. add d to the ans because this are the edges we are gonna remove to separate vertex v from the connected component. after this update degree of removed vertex and its neighbour vertex in hashmap and treemap. So, ans += d x++ 4) repeat step 3) till x becomes K and ans is our answer.
@@takeUforward I think,even if it has a cycle this algo should work. i.e. 1-2-3-1 1 -> 2 degree 2 -> 2 degree 3 -> 2 degree So smallest degree is 2, we can remove any vertex if k=2 then ans will be 2. (Ans += 2) For k = 3, now that degree of vertex 2 and 3 is 1 if we remove vertex 1. Ans += 1. Which is 3 edges.
@@antrapurohit8010 Seems to be correct. Remove the ones with smallest degrees, and remove the ones with degree 1, which will lead to one new component. But might fail in some cases where the minimum edges and part of the cyclic ones are same.
How about creating minimum spanning trees (MST) from the current x components and then using k-x to find the answer? The edges which create components will be present in the MSTs.
I am trying to rewrite a big number library I wrote many years ago. I am trying to move it from 32 bit native low-level C code to 64-bit native low level C code. I have used it to do prime number mathematics, RSA encryption, and Diffie Helman key exchange. I use it as a driver to explain how these technologies work. I just want to see if there will be any performance boost going native 64-bit. I will probably have to use some assembly language.
I didn't finish the video yet but i think the algorithm is to find the connected components first, find the bridges with the low link value, and calculate the minimum edges that you need to move. And now i will finish the video and see if i 'm wrong hhhhh.
I think i have a edge case on which this approach or code should not work, lets say n = 4,m =4, edges are - [ [ 1,2], [2,3] , [3,4], [4,2] ] i'll try to draw it- 4 / \ 1__2/___3 and k = 2, which means 2 components and answer should be 1 for it as if you remove edge between 1 and 2 you have 2 components, but according to striver's approach this is cyclic component so first he will remove edges responsible for cycle that mean one edge than one more to edge removal for havig two components which means his code should give answer 2 while it should be 1. i have more example of this edge case but this is the simplest and should work to explain what i am saying.
I think this code will work on given edge case . Please have a look : #include using namespace std; mapind; vectoradj(1001); mapvisited; int main() { int n,m,k; cin>>n>>m>>k; for(int i=0;i>u>>v; adj[u].push_back(v); adj[v].push_back(u); ind[u]++; ind[v]++; }
This example 1-2-3-1 4-5-6 7-8-9-10-7-9 What if k is 8? It is better to remove the edges from square(3) instead of triangle (1) Because 1st component and 2 nd component will endup giving only 7 but we need another to get that we have to remove 3 edges from square and totally it ends up removing 8 But if we consider square rather than triangle it ends up only removing 7 edges I think we also should consider what is max number of components we can get by removing the edges from cycle instead only checking for minimum edges to remove Correct me if my solution is wrong 😅
Please correct me if I am wrong. This is a greedy approach. We create a list. We store all the degree of node into it and list of node connected with that node. We declare an integer ans=0; Now for minimum removal of edge to get k component, we iterate through array and find minimum degree of node. while(k>0) { k--; ...................... } And add that degree in ans. After finding, we have to update array because that node is disconnected.
Nice solution, although I think there are few cases where this solution will not work, let’s say we have a fully connected component of 10 nodes and K=2, so the optimal answer would be 9, but with strivers solution we would get 37 ig. I think this is a NP Hard problem, as if we calculate the answer for K = 1 to N, then we can solve the clique problem using that information. Can you please share the resource of this problem and the solution given by the author if possible.
One simpler solution that I feel would work is, maintain degree of each node, a new component is created only if we cut a node whose degree is 1, if a node has degree more than 1, say x than x+1 edges need to be cut , so this generates the greedy algo, maintain a multiset of (degree,node) and remove the node which has min degree and accordingly adjust the degree of its neighbours. If anybody feels it wont work, feel free to mention some test
Seems an easier one, good way to think of it in this way..Am still thinking if this will give me the minimum or not, because of the following thought process. We might end up reductantly removing too many edges unnecessarily just because of the cycling thing. Need to sit back and think of some cases, but seems a good way to approach.
@@takeUforward One case where it fails, I just thought is what if more than one node has same minimum degree, which should i choose and came with a test and this algo fails. One way i thought it can be fixed is select that node whose component is lexicographically smallest when i arrange all nodes of a component in increasing order. What do you think?
@@vaibhavdawra8960 This is nice a thought , but this would fail in cases where you have multiple nodes with same degree , decision of choosing the node to disconnect would ultimately affect your answer. For example, current node with min degree that you decided to disconnect would be connected to some other nodes which are still in the cycle. While at the same time there may be node with same indegree that is connected to nodes which are not in cycle which you missed to choose at first
for the loop checking and knowing whether the edge could give me separate component i was thinking of union-find algorithm.even we can check for component using union find algorithm.
1)We maintain a priority queue of vertex where the priority deciding factor is the total degree of that vertex 2)Then we extract the min element (min degree) and separate that from the whole graph which would give me a new component 3)Then after removing that element from graph, I will update the whole graph and my priority queue and keep on doing that until I get K separate components. Please reply whether this algo will work or not?
,first we count number of connected components if connected components are greater than k,then print-1 else the solution always exist so,M-(n-k)+k will give minimum number of edges
Can we not use minimum spanning tree to solve this My idea is we find the number of components and if they are already greater than k, we print -1 Else we want to start disconnecting our graph until we get a component count of k We can use DSU to make it happen In MST instead of choosing edges with least weight we choose all the edges max weight until we get component count =k and after that juncture, there are two options either we come across an edge that increases the components then we have to add it’s cost in answer and other edge connects nodes belonging to the same disjoint set. Some one Please let me know if that would work Thanks
I have question on this. if you think of the case of : 1->3->7>5->3->8->10 .In this case there is a cycle in that component but on removing edge just 1 edge 1->3 or 3->8 or 8->10 we successfully get an extra component without affecting the cycle? Sorry Incase I am wrong. bhaiya please answer this
Hey, can you also post the actual solution to this problem? I wonder how you even satisfied with his solution because in my opinion two things actually matter for any algorithmic interview: 1. Correctness of the Algorithm 2. Complexity Analysis. First of all, where is the correctness? I wonder, that you asked for an algorithm, and you didn't even ask whether it's correct or not? It will also be helpful for the viewers who watch this video if you include the above two points.
All such videos only expose my lack of knowledge in basics even though am an "experienced" developer. I know I can escape the field without this much core knowledge. But the con is I would never end up working in Google or Microsoft , which is fine I guess. But this was fun to see how experts think.
Before this video I thought solution should be complete in less line of code and I practice since last 6-7 months. Now I can say for first solution lines of code is not important first fall get solution (brute force) and optimise it. Some how I also cramming the solution because I want to just complete the task but and I know this is not best way to practice but I did. Now striver again remembering me to think all possible ways as much as you can to solve a problem is real DSA 😊 thank a lot ❤
@@aayushgupta700 thanks for the question. There are three persons out there 1 code with Harry : best for cpp basics and oops concepts 2 love babbar : 149 video of DSA , he almost cover most of the interview questions. 3 striver : no doubt he should be at first place as I am think now ( after spending almost a year) but as beginner I even unable to understand what he is saying. His level is for experience person in my point of view. Now I watch striver because somehow I feel I am capable of understand his video lectures. But striver shorts videos are very useful for beginners => A pathway Every one is most respected person in my eyes. ☺️☺️
@@echocoding4550 thankz sir for replying sir I am in new in coding just now I had completed my sem 1 exam in eng but in sem 2 there is language called c so should I start learning c and then c++and after do the dsa plzz reply 🙏
This solution would fail for this case N = 7 , M = 8, K=2 Edges -> 1-2 , 2-3 , 3-4, 4-5, 5-6, 2-7, 3-7 your algo would give 3 but the right answer is 2 (last 2 edges can be removed)
I also think about it while seeing the vedio. Might be it works on directed graph. But what if we consider the edge as indegree of one node and outdegree of another connected node. And use heap and remove the nice having min sum of in degree and out degree , In case of undirected graph
Testcase: a complete graph! Brute: Try out all possible combinations starting from k-conncted_components edge sets to greater no edge sets until k connected components. Better approach: find bridges, if no. of bridges less than equals k-connected_components then boom 💥. Other wise delete all bridges then keep deleting edges from cycles or combination of cycles greedily i.e. edges whose sum of degrees of vertices is minimal. Best approach: design an algo for quantum computer, ll solve in linear time probably 😉 : 45min interviews p kaun aisa pucht h bhai
This problem is too hard to solve for the constraint of 1e5. I have a valid reason for it. K=2 this problem is equal to minimum cut == maximum flow. if you solved it, you find a liner maximum flow algo. This is enough to prove its impossible to solve it, maybe possible in Polynomial time but not for the constraint that n,m
What happen if removing 2 cyclic edges frees 5 edges which then don't contribute to the cycle then we can get 7 minimum But if we try to remove minimum contribution to cycle suppose 1 edges and gets 2 free edge We have now 3 Now again we again remove 1 and again got 2 We get 6 Again we remove 1 and get 1 tree edge We only get 5 components on removing 3 cyclic edges But same can be get by removing 2 extra edges and get 5 components so total is 7 So I think this solution will fail Please kindly check
Here is an algorithm I came up with under the assumption that the graph is simple: Let us first decompose the graph into connected components, now we may observe that If a connected component with x nodes has more than x-1 edges , deleting a single edge will not lead to an increase in the number of components. In other words we can say that for each connected component to really contribute to our result i.e cause an increase in number of connected components it must be in the form of a tree. So This leads us to greedily do the following: For each connected component we first figure out the minimum number of edges to delete such that it forms a tree Then we just keep disconnecting edges from each of the components in order of the number of edges required to make the component in form of a tree until we make k components @takeUforward is this algorithm correct?
This seems to be unsolvable problem for an interview. We can easily find the maximum number edges to be removed to get k connected components to find minimum probably we need min cut algorithm per component which will give us minimum number of edges to be cut to get two components and we can again run min cut algorithm on the child components produced. Time complexity will be much more, similar to Dinics algorithm each component.
One more test cases 1-2-3-4-5-6-3 (here is cycle) but we don't need to first remove cycle thing. We can first cutout the nodes to make one more components
Just curious to know this even though you've mentioned that this question won't be asked in an interview. We're you able to solve it or knew the solution just like interviewers know the solution of the DSA question they ask.
I was thinking instead of breaking the edges, we keep track of components while creating the dsu. suppose we iterate over edges and my_components are greater than k, so we take it but if our components =k then we take only edges which doesn’t effect the count of components
Not in this life i could ever come up with a counter question seconds after the interviewer gives me the problem. The way he asked what if number of components>k. That really got me and every single viewer of this video I'm sure😂🫶
how some people prepare their mind for such hard questions? ? I think the age old saying is true that Some are god-gifted. Because nobody can by himself be so keen on solving hard questions with a smile on his face
Initially I thought it was easy, until I figured out the edge case. Probably could have been a cleaner implementation if the camera pressure was not there :P. But this is what time constraint does to you. It was an amazing experience :)
Bhaiya ❤you are my saviour ❤your sheet and videos helped alot to gain knowledge ❤
The interview plus camera pressure is next-level! Being able to do this much proves that you truly are an expert in DSA (specially Graphs!)
What would the solution be if we change the question to - Find the number of edges to be removed such that the sum of weights of removed edges is minimum?
Thank You
Nice explanation and I thoroughly enjoyed the problem solving part, one edge case I could think this is missing is the component can have both cyclic part and non cyclic part, so greedily first we have to remove non cyclic edges within a component and then start removing cyclic edges and so on. What do you say?
I am so satisfied to see Raj writing code. I wonder, how much effort it would take to reach a place where he is. It's so inspiring to see him :)
We don't write code like that in a real job though. There we have a lot more interfacing and abstractions.
I don't know how or why I always fall for striver's way of solving problems, but he is a legendd!!! Thank you keerthi
+1
william lin sitting in corner :- hold my beer!
@@yamangoyal7629 tourist sitting in corner :- hold my codeforces and codechef rank
@@yamangoyal7629 Tourist to william lin : Do u know who i am?
@@yamangoyal7629 let him sit corner . Itna kuch khass nhi he
The given solution misses one edge case, imagine a component with 1 - 2 - 3- 4 - 5 - 3 , in this component we have a cycle, but still if we remove just the 1-2 edge, it will split them into two components. The correct solution seems to be the one where we end up removing the nodes with the smallest degrees, and then keep doing till we get the answer. This might also have some edge cases, need to grill on it. Minimum degree edges which are not a part of cylce, is what we have to grill on, does not seems that easy..
Even this does not work,
Consider follwing case
n=9 m=12 k=4,
1-2
2-3
3-4
4-1
5-6
5-7
6-7
6-8
6-9
7-8
7-9
8-9
Now, smallest degree is 2 for nodes 1,2,3,4,5 . Now if you select 5 first, then required edges to be removed is 4 but if you select apart from 5, required edges will be 3. So it depends on which node with minimum degree you select
@@vaibhavdawra8960 Yes it has be a combination of smallest degree and not part of cycle, seems a complicated one.. Tougher than it appears..
Exactly thought the same, you need something like topological sorting and also keep track of which compos contain cycle, and calculate accordingly, I guess this solution would be a bit more trickier than the one you wrote😜
I believe this question has to do something with bridges.
@takeUforward I think solution would be to find the bridges, each bridge would give you 1 more component(as it's an undirected graph it would be connected), If we fall short, we need to maintain indexed min heap of vertex's as all the components would be cycles and remove vertexes with minimum degrees, update the remaining degrees of adjacent vertexes and repeat till we reach #of Vertexes. (Max number of components in a given graph).
I found Keerti also confused 🤔 in middle of this video when striver explain Keerti expression like what he doing 😅 anyone thinking same like....
He may not be able to come up with the 100% accepted solution which is probably hard for a problem like this in an interview or in front of a camera but what he said at the end is 100% correct. Interviews are just not about if you were able to solve a probem but how you approach a problem.
What about this solution.... You count the indegree of all nodes. Subtract the 'k' from total components. That becomes your target. Now keep on visiting those nodes which has minimum indegree greedily. Disconnect them and add their indegree to the answer. Visit the immediate neighbors and decrease their indegree by 1. Seems to work on all test cases I came across.
You are on the right path, just keep improving on this. It's a good start and a lot better than the attempt made by striver in the video
n=8, m=9, k=2
1 2
2 3
3 4
4 1
3 5
5 6
6 7
7 8
8 5
Try on this test case.., you answer would be *2* (minimum indegree is 2 here), but u can just remove the 3-5 edge to make 2 companents. So, actual ans is *1*
@9:39 5-6 6-7 7-8 won't break the component , they are part of the cycle too as 8-5 is. Just find all the cycles in the graph and keep the list of edge not in any cycle. After that you can also find the edges with which you can have your prob solved in minimum cost not just minimum number.
Yes you are correct. That's what I replied. Each edge is dependent whether the other edge has been already removed or not. Even removing 6-7 will not break the component.
@@surajmamgai102anybody please tell me which programming language striver bhai uses to solve the problem in this video..I'm completely new so ...c,c++ or java
@@maheshvommi1092 It's C++ bro. If you are new then you might find syntax different here bcz of the use of STL's and bits/stdc++.h library.
its c++@@maheshvommi1092
@@maheshvommi1092 c++
my approach:
1). count no. of components - x
if x>=k return -1
2). so, we need to make the k-x components
3). calc the degree of all the node and put it into treemap, tm
4). take a variable ans =0 for min #edges need to remove
5). iterate over treemap until x
Is this approach functioning correctly?
We can utilize the property of bridges because as per definition "a bridge is an edge which on removal increases the number of connected components by one".
The procedure I have thought of is,
1. We have to make k connected components.
2. Let the current number of connected components be 'curr_con', now 'k-curr_con' more components to make.
3. Count the number of bridges available in the graph (using DFS), let it be 'b' and break the bridges, now ' k-curr_con-b' more components to make.
4. Now again find the number of bridges, break them and keep on repeating this until we make it to k connected components.
It wont work
@@knowcode6374 Can you please explain why ?
It will fail where we have to remove the edge in the cycle to get the required k component.
@@varungurnani4989 kosa Raju algo we can use I think, no of strongly connected components
@@varungurnani4989 It will fail when there is no bridge present at the moment, for eg, a square has no bridge, therefore it will lead to an infinite loop of checking same graph structure again and again.
My approach
1) create an adjacency matrix for all the nodes in the graph using DFS.
2) while DFS, find the total number of islands/components present in the graph by having the visited vector (let us assume total components = x).
3) (k-x) is the required number of extra components. and ans=0.
4) start a loop for (k-x) times.
4) parse the adjacency matrix and find the node that has the lowest degree (least number of adjacent nodes)
5) Add the degree to the ans (this separates this node into a new component)
6) also remove the current node from the adjacent nodes. (updating the adjacency matrix after removing nodes)
7) return the final ans.
@@user-rn1yb5pq8k that would be wrong as you are having a greedy approach.
Which would not work for some edge cases.
Like
Imagine you have 2 big clusters of nodes and they are connected to eachother inside the cluster now also let both of them to be identical and now let a node be added to any one cluster so that it is connected to 3 nodes
And now the time is to connect the 2 clusters select 2 nodes from both the clusters except the 3 one that we added.now make the graph a single component by connecting the 2 components that we had originally
Now you have a graph
So if k=2
All you req is to sever that final edge that you had so your answer should be one
But from your algo we should remove the 3 edge node
If you are able to understand this case then good .other wise I may answer it in more detail
I kept trying to think and solve along. Now I am just glad I was able to follow along and understand 😝
Learnt a lot of tackling from this video. Thanks Keerti and Striver!
Assalamualaikum
Tamila bro
@@mehranmushraf5224😂😂😂
Lots of respect to Striver writing so much code to guide us through.
However suppose the graph initially has only one component which is densely connected with a lot of edges and k=2 that is you have to remove some edges so that you get one more component. In this code first you would end up removing all the edges that are causing cycle in the graph and 1 more edge to make a new component. But it is possible it is not the minimum number of edges required to make 2 components but far more than the actual answer. Am I wrong somewhere?
Asking constraints for n to understand the time complexity and understand which algorithm can be fit there ...is something I loved most ....I never knew this trick can be useful in interview
Adding one more thing ....not giving up and trying to write code even if it is not correct.....In my last interview I had 3 coding questions (1 easy and 2 medium) ..I was able to solve starting two with multiple approach but in last one I was only able to give brute force and better approach and while trying to give optimal solution I gave up ...and guess what ....I gave almost every answer I still got rejected due to giving up attitude....( Lesson learnt but hurtfully)
My Solution can be like finding all bridges in the graph using tarjan's algorithm for undirected graph along with that storing bi-connected components using stack . removing a brigde will surely give you a more connnected component. So Assuming initially there was a single connected component in the graph.If we got n bridges then we can get n+1 components . if n+1>k then we will delete only k-1 brigdes else if(n+1
Very good mock interview, Learned so many things.
I have one doubt in your example only.
1) 1 - 2 - 3 - 1
2) 4 - 5 - 6
3) 7 - 8 - 9 - 10 - 7 - 9
k = 8 (You took 7 but I took 8 because i thing here is an edge case).
From your code it will be 3 (already given) + 2 (more from 2nd compo) + 1 (cycle removing edge in 1st compo) + 2 (more from 1st original compo) + 2 (cycle removing edge from 3rd compo) + 1 (from 3rd compo)
edges req = 3 + 2 + 1 + 3 + 2 + 3 = 11.
components = 3 + 2(from 2nd) + 2(from 1st) + 1(from 3rd) = 8.
From my code it will be 3 (already given) + 2 (more from 2nd compo) + 2 (cycle removing edges from 3rd compo) + 3 (more from 3rd compo)
edges req = 3 + 2 + 2 + 3 = 10.
components = 3 + 2 (from 2nd compo) + 3 (from 3rd compo) = 3 + 2 + 3 = 8.
At the end , I got Answer with 1 less edge required.
So, I think that last greedy approach won't work every time, We need to check that how many requirements of componenets, according to that we need to break cycles and get more components from that component.
It means At Last, "The count of cycle breaking edges and getting components from it", this thing should be minimum instead of "only minising the cycle breaking edges".
Please check once and correct me if i am wrong.
Thanks for Fantastic mock interview.
This was fun to watch xD.
I think a more interesting problem would be to find out the minimum weight of the edges to be removed instead of the number of edges.
Also, I think there might be a mathematical solution for the "number of edges" problem wherein we look at the number of edges in each component and make some greedy choices.
Let’s do another mock interview where I ask you this level of question. What say ✌🏻
@@KeertiPurswani woohoo that would be awesome. I am down for it✌️
Yaaaay! Karte baat
@@PriyanshAgarwal mostly awaiting...
same thought about the problem statement
He is a great problem solver how logical thinking his brain has 🔥
I think Edmond Karp variation of Ford Fulkerson method to find the maximum flow between source and sink nodes which would be equal to min cut will work. We probably have to do it for all the possible pairs in the graph and then pick the one with minimum cut and then remove the edges from the graph. This will lead to 1 more disconnected component in the graph with removal of minimum cost of edges. Have to do this k - 1 times to have k components. Complexity goes somewhere around k * V2*(V*E2).
yes
Got a Solution -- using concept of degree and min heap Priority Queue
note -- maximum disconnected components = n (number of nodes) as constraint is 1 n-1) ;
4 - have a min priority queue storing ( {degree,node} ) ;
5 - push all nodes with their respective degrees ;
6 - pop() current node at each iteration do ct ++ ; ans +=degree[current] and for all neighbouring nodes degree - - ;
push them and do this til ct == k
7 - return ans ;
Broo☠️☠️
Broo☠️
It's O(n²logn) right?
This is the approach i could think of using UNION-FIND:Let me know if I am wrong ^^
We need to find the minimum number of edges that can be removed to get exactly k-connected components.
Consider it the reverse way: Find the max number of edges that can be joined to give you exactly k connected components.
Inittially consider all the nodes as individual graphs(consider each node as the parent of itself). USE UNION -FIND to join two nodes and check the number of components thus remaining(check number of unique parent nodes- make a parent array corresponding to the ). Keep a count variable to store number of edges covered.
There will be a point you reach where there will be exactly k unique parents. Keep going forward but this time only use an edge if on using it, two components of same parent are connected(because cycles won't increase the number of components). Only then increase count.
Count will be your answer.
Thanks u striver Bhaiya and keerti didi for making this video this is very helpful and interesting video how to approach problem, represent to our ideas and thought process to interviewer. 😍😍
Dayum! Just amazing
Watching striver’s interview was totally worth it
Thank u keerti and you have earned a new subscriber :)
Thank you! And welcome to the channel! Hope you like rest of the content as well 😇😇
Love you Striver Bhaiya your the King of Coding😍
Love u striver bhaiya. ❤ You are master in DSA. Currently I am watching your graph series. Awesome 👍
Idk but while watching this, I felt that the interviewer is more confused than the interviewee
It was great...want some more such interviews with Striver.❤
I think, we can use union find . If both a and b belongs to same parent then breaking a----b edge won't give us new components. This way we can keep track probably.
Hope you watched the whole video and noticed that he followed same approach!
Yes I watched the video. Great efforts put in by both . Thanks for the video 👍
we can also use Degree of a node in a graph property here .
NOTE : Here the cost is the no of edges that should be removed to make a new component
Approach :- we know that a node with a degree one can always give us a new component with a cost of 1 . A degree of node 2 give us new component with a cost of 2 and similarly for a component with a degree of n we get a new component with a cost of n .
So basically we need to spot the nodes with a degree one in the current formed graph , another thing is that when we remove a node we have to decrease the degree of all the nodes which are directly connected to it by 1 .
And then just iterate till the components are not equal to K along with adding the cost
Pls comment if there are any edges cases / logic error in the approach
Logic is wrong. If we consider this case when k = 2:
2 4
| \ / |
3 --7-- 6 -- 1
| / \ |
5 8
clearly, your logic would say the answer is 2, but the answer should be 1.
For the correct solution I think initially we should try to remove the bridges as removing one gives one new component guaranteed.Then if we still need more components,we are then left with disconnected graphs in which each one of the nodes obvously belongs to a part of a bigger cycle and there maybe smaller cycles including some subset of nodes in that component also.No idea how to proceed from this...😅
we could also remove articulation points also , ya but removing of a articulation point will take upto 2 edges at once.
@@pulkitjain5159can you please tell , striver bhai solving qus in which programming language..I'm new so I want to know
c++ @@maheshvommi1092
This is the correct Approach
what I have seen in almost other videos of keerti ,It was always like Keerti use to get Upperhand but here it was like Interviewer got nervosed by interviewee and Literally Striver Being Striver You knocked it Bro.Motivates me for Self-learning
Striver is a god damm monster 💀
I think there is an edge case in 7 - 8 - 9 - 10 - 7 - 9. We can remove 7-8 and then 8-9 then we have 1 more component = 8. So we don't really need to remove 2 edges to get one more component. Instead I would find the bridges. If a + bridges >= k thats a return. Else keep track of the sizes of cycles like in this case 3, 3. Then individually check for those cyclic components
Can someone please comment on below algorithm that I thought:
1) find no. of connected components. Let it be x.
2) find degrees of each vertices and store it in hashmap. also create a treemap.
3) remove any smallest degree vertex from treemap (that is why I took treemap to easily remove vertex with smallest degree). Lets say vertex v has smallest degree d. add d to the ans because this are the edges we are gonna remove to separate vertex v from the connected component. after this update degree of removed vertex and its neighbour vertex in hashmap and treemap. So,
ans += d
x++
4) repeat step 3) till x becomes K and ans is our answer.
How will you ensure that someone with the smallest degree is not form of a cylce, this is what I am thinking
@@takeUforward I think,even if it has a cycle this algo should work.
i.e. 1-2-3-1
1 -> 2 degree
2 -> 2 degree
3 -> 2 degree
So smallest degree is 2, we can remove any vertex if k=2 then ans will be 2. (Ans += 2)
For k = 3, now that degree of vertex 2 and 3 is 1 if we remove vertex 1. Ans += 1. Which is 3 edges.
i thought of exactly same solution, If you find any test on which it does not work , add it in ypur comment
@@antrapurohit8010 Seems to be correct. Remove the ones with smallest degrees, and remove the ones with degree 1, which will lead to one new component. But might fail in some cases where the minimum edges and part of the cyclic ones are same.
@@takeUforward thank you for your reply!!
How about creating minimum spanning trees (MST) from the current x components and then using k-x to find the answer? The edges which create components will be present in the MSTs.
wouldn't that have an issue with cyclic graphs?
I am trying to rewrite a big number library I wrote many years ago. I am trying to move it from 32 bit native low-level C code to 64-bit native low level C code.
I have used it to do prime number mathematics, RSA encryption, and Diffie Helman key exchange.
I use it as a driver to explain how these technologies work.
I just want to see if there will be any performance boost going native 64-bit. I will probably have to use some assembly language.
I didn't finish the video yet but i think the algorithm is to find the connected components first, find the bridges with the low link value, and calculate the minimum edges that you need to move.
And now i will finish the video and see if i 'm wrong hhhhh.
I think i have a edge case on which this approach or code should not work,
lets say n = 4,m =4,
edges are - [ [ 1,2], [2,3] , [3,4], [4,2] ]
i'll try to draw it-
4
/ \
1__2/___3
and k = 2, which means 2 components and answer should be 1 for it as if you remove edge between 1 and 2 you have 2 components,
but according to striver's approach this is cyclic component so first he will remove edges responsible for cycle that mean one edge than one more to edge removal for havig two components which means his code should give answer 2 while it should be 1.
i have more example of this edge case but this is the simplest and should work to explain what i am saying.
I think this code will work on given edge case . Please have a look :
#include
using namespace std;
mapind;
vectoradj(1001);
mapvisited;
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
ind[u]++;
ind[v]++;
}
priority_queuepq;
for(int i=0;i
This example
1-2-3-1
4-5-6
7-8-9-10-7-9
What if k is 8?
It is better to remove the edges from square(3) instead of triangle (1)
Because 1st component and 2 nd component will endup giving only 7 but we need another to get that we have to remove 3 edges from square and totally it ends up removing 8
But if we consider square rather than triangle it ends up only removing 7 edges
I think we also should consider what is max number of components we can get by removing the edges from cycle instead only checking for minimum edges to remove
Correct me if my solution is wrong 😅
you are right
Please correct me if I am wrong. This is a greedy approach.
We create a list.
We store all the degree of node into it and list of node connected with that node.
We declare an integer ans=0;
Now for minimum removal of edge to get k component, we iterate through array and find minimum degree of node.
while(k>0)
{
k--;
......................
}
And add that degree in ans.
After finding, we have to update array because that node is disconnected.
Nice solution, although I think there are few cases where this solution will not work, let’s say we have a fully connected component of 10 nodes and K=2, so the optimal answer would be 9, but with strivers solution we would get 37 ig.
I think this is a NP Hard problem, as if we calculate the answer for K = 1 to N, then we can solve the clique problem using that information.
Can you please share the resource of this problem and the solution given by the author if possible.
One simpler solution that I feel would work is, maintain degree of each node, a new component is created only if we cut a node whose degree is 1, if a node has degree more than 1, say x than x+1 edges need to be cut , so this generates the greedy algo, maintain a multiset of (degree,node) and remove the node which has min degree and accordingly adjust the degree of its neighbours. If anybody feels it wont work, feel free to mention some test
Seems an easier one, good way to think of it in this way..Am still thinking if this will give me the minimum or not, because of the following thought process.
We might end up reductantly removing too many edges unnecessarily just because of the cycling thing. Need to sit back and think of some cases, but seems a good way to approach.
@@takeUforward One case where it fails, I just thought is what if more than one node has same minimum degree, which should i choose and came with a test and this algo fails.
One way i thought it can be fixed is select that node whose component is lexicographically smallest when i arrange all nodes of a component in increasing order.
What do you think?
@@vaibhavdawra8960 This is nice a thought , but this would fail in cases where you have multiple nodes with same degree , decision of choosing the node to disconnect would ultimately affect your answer. For example, current node with min degree that you decided to disconnect would be connected to some other nodes which are still in the cycle. While at the same time there may be node with same indegree that is connected to nodes which are not in cycle which you missed to choose at first
@@user-le6ts6ci7h Yep, realised that and also proposed an alternative in this thread. What do you think about that?
Inspirational and so motivational video. So much knowledgeable. Thank you.
Striver is on fire. Lately he is doing best collaborations.First kirti and now harkirat 🙌🙌
Suppose we have 2 components:
(i) 1-2
(ii) 3-4-5-6-3 (cyclic)
If k = 4 then the answer should be 3 but if we do k-x then we are getting 2
X is 1 one, as the cyclic ones will not be counted, watch the entire video, I have covered this edge case as well
@@takeUforward yeah! Watched the complete video.
Understood! 😊
for the loop checking and knowing whether the edge could give me separate component i was thinking of union-find algorithm.even we can check for component using union find algorithm.
take mock coding interview with love babbar
Striver sir ❤ you are legend....pata nehi apke jaise kabhi ban pauga or nehi...🙏🙏🙏
Everyone forgets, this line give me the hope😄
1)We maintain a priority queue of vertex where the priority deciding factor is the total degree of that vertex
2)Then we extract the min element (min degree) and separate that from the whole graph which would give me a new component
3)Then after removing that element from graph, I will update the whole graph and my priority queue and keep on doing that until I get K separate components.
Please reply whether this algo will work or not?
is it like kahn's algorithm
,first we count number of connected components if connected components are greater than k,then print-1 else the solution always exist so,M-(n-k)+k will give minimum number of edges
Can we not use minimum spanning tree to solve this
My idea is we find the number of components and if they are already greater than k, we print -1
Else we want to start disconnecting our graph until we get a component count of k
We can use DSU to make it happen
In MST instead of choosing edges with least weight we choose all the edges max weight until we get component count =k and after that juncture, there are two options either we come across an edge that increases the components then we have to add it’s cost in answer and other edge connects nodes belonging to the same disjoint set.
Some one Please let me know if that would work
Thanks
Tarajan's algorithm for articualtion point and bridges!
Next with Kunal Kushwah please
I have question on this. if you think of the case of : 1->3->7>5->3->8->10 .In this case there is a cycle in that component but on removing edge just 1 edge 1->3 or 3->8 or 8->10 we successfully get an extra component without affecting the cycle? Sorry Incase I am wrong. bhaiya please answer this
What is the edge weight for? 😅
Hey, can you also post the actual solution to this problem? I wonder how you even satisfied with his solution because in my opinion two things actually matter for any algorithmic interview:
1. Correctness of the Algorithm
2. Complexity Analysis.
First of all, where is the correctness? I wonder, that you asked for an algorithm, and you didn't even ask whether it's correct or not? It will also be helpful for the viewers who watch this video if you include the above two points.
All such videos only expose my lack of knowledge in basics even though am an "experienced" developer. I know I can escape the field without this much core knowledge. But the con is I would never end up working in Google or Microsoft , which is fine I guess.
But this was fun to see how experts think.
Amazon and Google you can
@@GOJOANDSUKUNAFAN No bro, am not worth that much. I realised in few years back 🙂
@@thiruvetti may be they aren't worth of you.
@@lohithreddy5356 Thaks for postive words but am poor in DSA skills.
@@thiruvetti It's not that you are poor in dsa it's that you are poor at giving time to dsa, take some/lot of time to grasp.
enough motivation to continue the graph series 😭😭
Before this video I thought solution should be complete in less line of code and I practice since last 6-7 months. Now I can say for first solution lines of code is not important first fall get solution (brute force) and optimise it.
Some how I also cramming the solution because I want to just complete the task but and I know this is not best way to practice but I did.
Now striver again remembering me to think all possible ways as much as you can to solve a problem is real DSA 😊 thank a lot ❤
Where did you learn dsa and which programming language
@@aayushgupta700 thanks for the question. There are three persons out there
1 code with Harry : best for cpp basics and oops concepts
2 love babbar : 149 video of DSA , he almost cover most of the interview questions.
3 striver : no doubt he should be at first place as I am think now ( after spending almost a year) but as beginner I even unable to understand what he is saying. His level is for experience person in my point of view. Now I watch striver because somehow I feel I am capable of understand his video lectures.
But striver shorts videos are very useful for beginners => A pathway
Every one is most respected person in my eyes. ☺️☺️
@@echocoding4550 thankz sir for replying sir I am in new in coding just now I had completed my sem 1 exam in eng but in sem 2 there is language called c so should I start learning c and then c++and after do the dsa plzz reply 🙏
This solution would fail for this case
N = 7 , M = 8, K=2
Edges -> 1-2 , 2-3 , 3-4, 4-5, 5-6, 2-7, 3-7
your algo would give 3 but the right answer is 2 (last 2 edges can be removed)
That moment, when the interviewee outshines the inteviewer \m/,
Striver bhiya is emotion❤ DSA main bhoot confident hogya hu Inki vajah se
Where u learn concepts
@@DeepakLalchandaniProfile take u forward channel
Please take a mock interview of love babber ❤
we can find the degree of each node and remove the edges from nodes which have less degree using Heap
Does not works, minimum edges with redundancy will be an issue, unfortunately.
I also think about it while seeing the vedio. Might be it works on directed graph.
But what if we consider the edge as indegree of one node and outdegree of another connected node. And use heap and remove the nice having min sum of in degree and out degree , In case of undirected graph
I write nice instead of node (type error)
Testcase: a complete graph!
Brute: Try out all possible combinations starting from k-conncted_components edge sets to greater no edge sets until k connected components.
Better approach: find bridges, if no. of bridges less than equals k-connected_components then boom 💥. Other wise delete all bridges then keep deleting edges from cycles or combination of cycles greedily i.e. edges whose sum of degrees of vertices is minimal.
Best approach: design an algo for quantum computer, ll solve in linear time probably 😉
: 45min interviews p kaun aisa pucht h bhai
03:08 all time i was thinking hey man first remove this space before word exactly k connected graph
Subscribed! thanks for bringing striver!
I will think about answering this question once I am done with my preparation. It's going to be my mock interview at that time
Haha man ki batt chin Li.
Kas esa hota.
Feels like he started teaching her😂
This problem is too hard to solve for the constraint of 1e5. I have a valid reason for it. K=2 this problem is equal to minimum cut == maximum flow. if you solved it, you find a liner maximum flow algo. This is enough to prove its impossible to solve it, maybe possible in Polynomial time but not for the constraint that n,m
46:45 to just revise whole code ❤
Two of my favourite youtubers in one video.
🧡
What happen if removing 2 cyclic edges frees 5 edges which then don't contribute to the cycle then we can get 7 minimum
But if we try to remove minimum contribution to cycle suppose
1 edges and gets 2 free edge
We have now 3
Now again we again remove 1 and again got 2
We get 6
Again we remove 1 and get 1 tree edge
We only get 5 components on removing 3 cyclic edges
But same can be get by removing 2 extra edges and get 5 components so total is 7
So I think this solution will fail
Please kindly check
Why not remove 2 edges from cycle to get 2 components, instead of removing component with 1 cycle
striver is a living legend i guess he solved problem during his sleeping time too 🤣🤣🤣🤣🤣🤣
Here keerthi dd is confused and frustrate than striver bhai
Here is an algorithm I came up with under the assumption that the graph is simple:
Let us first decompose the graph into connected components, now we may observe that If a connected component with x nodes has more than x-1 edges , deleting a single edge will not lead to an increase in the number of components. In other words we can say that for each connected component to really contribute to our result i.e cause an increase in number of connected components it must be in the form of a tree.
So This leads us to greedily do the following:
For each connected component we first figure out the minimum number of edges to delete such that it forms a tree
Then we just keep disconnecting edges from each of the components in order of the number of edges required to make the component in form of a tree until we make k components
@takeUforward is this algorithm correct?
I thought of the same solution
I am very much convinced that greedy solution will work
Any test case in mind it might fail on?
Hi Keerti, can u give the link of the question please? I have a solution in mind. Just wanted to test it.
He can decrypt imagination into code 👌
I don't understood who's the interviewer... keerti or striver XD
😂😂
you both should get married eachother 🎉
Keerti didi next love babbar.
Bolo unko!
@@KeertiPurswani unse na ho pyega
@@shivamarora7422 then what about kunal bhai
This seems to be unsolvable problem for an interview. We can easily find the maximum number edges to be removed to get k connected components to find minimum probably we need min cut algorithm per component which will give us minimum number of edges to be cut to get two components and we can again run min cut algorithm on the child components produced. Time complexity will be much more, similar to Dinics algorithm each component.
Neither I am a programmer nor from a CSE background, I am here for Kirti's innocent voice 😁😁
Simp
I think this testcase missed
1-2-3-1 => 3 nodes (1 edge removal will give acyclic)
4-5-6-4 => 3 nodes (1 edge removal will give acyclic)
11-12-13-14-15-16-17-18-19-20-11-13 => 10 nodes (2 edge removal will give acyclic)
k=10
already=3
left=7
Acc. to @striver (ans=0)
- remove 1 edge component (ans=1, left = 7) then remove edge (ans=3, left=5)
- remove 1 edge component (ans=4, left = 5) then remove edge (ans=6, left=3)
- remove 2 edge component (ans=8, left = 3) then remove edge (ans=11, left=0)
But if we remove 2 edge component (ans=0)
- remove 2 edge component (ans=2, left = 7) then remove edge (ans=9, left=0)
52:15 - I think here it's 1,7
One more test cases
1-2-3-4-5-6-3 (here is cycle) but we don't need to first remove cycle thing. We can first cutout the nodes to make one more components
Just curious to know this even though you've mentioned that this question won't be asked in an interview.
We're you able to solve it or knew the solution just like interviewers know the solution of the DSA question they ask.
Bhai kon kiska interview le rha hai
Hi , Please could you provide us some more difficult questions with solutions.
can i get the link to the solution i don't think the answer is correct and i don't seem to find the question on google.
I was thinking instead of breaking the edges, we keep track of components while creating the dsu. suppose we iterate over edges and my_components are greater than k, so we take it but if our components =k then we take only edges which doesn’t effect the count of components
Not in this life i could ever come up with a counter question seconds after the interviewer gives me the problem.
The way he asked what if number of components>k. That really got me and every single viewer of this video I'm sure😂🫶
You will be. I am pretty sure. It’s just matter of time and practice! 😇
Hopefully!
thanku for the sharing the mock interview with striver
I didn't understand the question 😂
how some people prepare their mind for such hard questions? ? I think the age old saying is true that Some are god-gifted.
Because nobody can by himself be so keen on solving hard questions with a smile on his face
13:30 I was able to figure out the edge case.
I think for this question degree of vertex and alredy have components needed.
Correct me if I am wrong
That greedy approach in the last wouldn't works for all cases.
Btw done very well Striver!!
Hard question for me..
And plus keerti g in dominating mode 🥺
Striver is legend in coding community.