Number of Operations to Make Network Connected | Leetcode

This video explains a very important graph interview problem which is to find the minimum number of operations to make a network connected.This is an important graph algorithm problem which is frequently asked in programming interviews.This is from Leetcode 1319. In this problem, I have first explained the goal and then taken some examples to clear the understanding of the problem.I have then shown how this problem is related to the minimum spanning tree.I have also shown the concepts of redundant edges and also how to use them to find the minimum number of operations to make the graph connected.I have also shown the solution steps and a simple dry run of the algorithm.At the end of the video, I have also explained the code walk through of this problem.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKS:-
MST: • Spanning Tree | MST | ...
DFS: • Depth first search | D...
#graph #leetcode #graphalgo

[@tejasnakhate]

You can expect a follow-up question here as to print the new edges made to connect network to one component.

[@manishsalvi2901]

I did the same thing.
But I ignored counting number of redundant edges because as it has number of edges greater than n-1 then it will definitely form a connected graph.
here is what I did
class Solution {
public:
void dfs(int i,vector &visited,vector &connections)
{
visited[i]=true;
for(int u:connections[i])
{
if(!visited[u])
dfs(u,visited,connections);
}
}
int makeConnected(int n, vector& connections) {
vector adj(n+1);
for(int i=0;i

[@techdose4u]

👍

[@nitinkumar5974]

Awesome & Mine Blowing Explanation THANK YOU so much....brother ♥

[@adityaojha2701]

Thank you Sir for such a great explanation!!♥

[@techdose4u]

Welcome ☺️

[@prasannapm3220]

Very well logic was built up , thank you

[@raviashwin1157]

After seeing the intution,i was able to code myself,thanku so much❤️

[@techdose4u]

Great

[@amanarora8746]

here counting the number of components is similar to what we did in leet code P. No 547, counting the provinces?

[@sulthanmogal9692]

Than that many checks, we can do this :
if (connections.length >= n-1) return totalComponents-1;
else return -1;

[@kp_nagar]

great explanation
second way is negative case check karte number of component -1 is inf for it.

[@techdose4u]

👍🏼

[@impatientgaming9868]

Good one

[@srishtisuman2561]

Loved the explanation

[@sharuk3545]

Awesommm explanation bro 🤜 thnk u sooo much

[@techdose4u]

Welcome :)

[@lokeshsenthilkumar4522]

Hi Sir..can I ask u what tool are you using as a digital board?

[@mohdfarman3470]

Great Explanation❤❤

[@nikhil7129]

Best explanation ❤

[@joydeeprony89]

Great explanation

[@JohnSmith-uu5gp]

Awesome!

[@ekengineer9868]

why so clear man

[@ashokk2002]

Sir, why to again create an adjacency list ... Can't we use the graph already given in the question

[@shivammehta9661]

Very Nice Work

[@techdose4u]

Thanks

[@mohitmanuja7239]

Hi,
As we already checked that min number of edges required are n-1, so if there are n-1 edges present then we can simply return components-1 as result rather than finding redundant.
Is my understanding correct, if not can you explain..??

[@ashishkhoiwal9330]

at 5:08 did you mean "All extra edges are redundant"?

[@nasimahmedbulbul4401]

Redundant part can be ignored as if edges>=n-1 there is an solution for sure. Then we can just return components-1;
Solution:
class Solution {
public:
void DFS(unordered_map&adj, int curr, vector&visited){
visited[curr]=true;
for(auto it: adj[curr]){
if(visited[it]==false){
DFS(adj,it,visited);
}
}
}
int makeConnected(int n, vector& connections) {
vectorvisited(n,false);
unordered_mapadj;
int edges = connections.size();
if(edges

[@uditagrawal6603]

MST cannot be formed of disconnected graph, so here we are trying to form MST like structure for multi component graph?
Am i right?

[@techdose4u]

MST for a single component graph is feasible.

[@uditagrawal6603]

@@techdose4u Yes but here we are dealing with multiple components, so is MST for multiple components is feasible?

[@techdose4u]

No. In such problems you have to use DSUF in combination to keep track of components.

[@guptashashwat]

Read the hints given in LC ques and return number of connected components - 1. Ans.

[@priyaverma7976]

Sir it would be helpful if you would do interviewbit questions like you do for leetcode ones

[@techdose4u]

Actually all interviewbit questions are taken from leetcode. So doing leetcode will cover them both.

[@priyaverma7976]

@@techdose4u okay, thankyou sir

[@harishwarreddy9114]

It is an easy problem , we want some good questions sir

[@techdose4u]

👍

[@seyidaniels1350]

Awesome! First Comment

[@techdose4u]

😀

[@shivamrastogi8146]

redundantEdges (r) = Total Edges (E) - ( (n-1) - (c-1) )
for answer to exist: r >= c-1
Put value of r from first eqn into second eqn and solve.
You will get E >= (n-1) which we have already checked earlier.
So there is NO NEED to check if r>=c-1 or not.
If E>=n-1 some answer will always exist!

[@davissebastian4799]

vcool

[@techdose4u]

👍🏼

[@simrankureel94]

It is giving TLE, don't know why ?

[@aadishkapoor8088]

use vectoradj[ n] instead of using map for storing adjacency list. Just write this in place of unordered_map adj and it should work fine

[@Arya-nc4rg]

Hey guys I want some companion in coding so that if we have doubts regarding any questions so we can help each other. So are you interested to join us

[@yashgaur1716]

@@aadishkapoor8088 That was really helpful, Thanks brother