1579. Remove Max Number of Edges to Keep Graph Fully Traversable || Union Find || DSU || Graph

In this video, I'll talk about how to solve - 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Minimum Cost of a Path With Special Roads || Union Find || Disjoint Set Union || DSU || Graph

Let's Connect:

Resources you can try:

🎥Channel Playlists

About Channel:
We teach about how you can grow in life & educate about programming in Fun & Intuitional way.

About Me:
I am Aryan Mittal - a Software Engineer, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)

✨ Timelines✨

✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[anonnona]

I tried to code it by myself, without looking at any solution approaches or hints or anything remotely like that. But I had to come here for your video at last when my code had passed 84/85 test cases. Dil ka dard bayaan nahi kar sakta main.

[rupdeepthey]

You uploaded a video each day this month. Helped a lot. Thanks and keep up the good work!

[rev_krakken]

DSU was very intuitive and I was able to solve it easily using it

[priyankajhamb]

Greetings,
Thankyou, you made the concept of union find interesting and your code-snippet is also helpful.

May u can tell why this is occuring like
sort(edges.begin(), edges.end(), [&](auto const &a, auto const &b){
return a[0] >= b[0];
});
is giving me the heap buffer overflow error but after removing equal to sign
sort(edges.begin(), edges.end(), [&](auto const &a, auto const &b){
return a[0] > b[0];
});
the code is working fine.

[lvisbl__]

I understand why we need to choose edges of type 3 first, but do the order type 3 edges is matter? For example we have 10 type 3 edges, we need to figure which type 3 edges to choose first to maximize the number of type 3 edges chosen.

[cheguevara]

your explainations was very good and really help me to understand the approach, one suggestion is that you could try to calm or maintain you body language which is anoying

[shauryaraghuvanshi]

why for type =3 we are dsu of alice only shouldn't we check for both

[anonnona]

Hello Aryan I have a doubt, I tried to check if graph was traversable by Alice and Bob by seeing if number of i's in parent array such that parent[i] == i is equal to 1 or not. I hypothesized that if graph is traversable, then it must contain only one parent[i] such that parent[i] == i. But apparently there was a test case where there only existed one such i in parent[i] for both Alice and Bob such that parent[i] == i; but graph was not traversable by both/one of them; so my code was giving wrong answer where it should have rather given ans as -1. Any help please? Thanks for this channel btw love your videos.

My solution passed 84/85 testcases, just didn't pass this one.

The test case was :
n = 13

[[1, 1, 2], [2, 2, 3], [2, 3, 4], [1, 3, 5], [3, 2, 6], [2, 3, 7], [3, 7, 8], [3, 2, 9], [2, 4, 10], [2, 9, 11], [1, 2, 12], [3, 4, 13], [2, 2, 7], [1, 1, 9], [1, 2, 13], [2, 7, 13], [3, 2, 3], [1, 7, 10], [2, 8, 11], [1, 2, 7], [2, 1, 9], [2, 2, 9], [1, 5, 6], [2, 4, 9], [1, 7, 8], [1, 4, 6], [1, 4, 9], [3, 7, 13], [2, 2, 8], [2, 2, 6], [1, 1, 10], [1, 1, 11], [2, 5, 10], [1, 2, 9], [2, 1, 2], [1, 3, 4], [3, 6, 8], [3, 6, 13], [1, 3, 8], [1, 1, 6], [3, 3, 9], [1, 2, 3], [1, 11, 13]]

[sahebsarkar]

One suggetion for you don't move your hand or your body to much it create disturbance other wise content is next level.