Number of Operations to Make Network Connected | Leetcode

[@tejasnakhate]

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

[@amanarora8746]

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

[@joydeeprony89]

Great explanation

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

👍

[@adityaojha2701]

Thank you Sir for such a great explanation!!♥

[@techdose4u]

Welcome ☺️

[@ashishkhoiwal9330]

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

[@lokeshsenthilkumar4522]

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

[@raviashwin1157]

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

[@techdose4u]

Great

[@impatientgaming9868]

Good one

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

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

👍🏼

[@mohdfarman3470]

Great Explanation❤❤

[@sharuk3545]

Awesommm explanation bro 🤜 thnk u sooo much

[@techdose4u]

Welcome :)

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

[@JohnSmith-uu5gp]

Awesome!

[@prasannapm3220]

Very well logic was built up , thank you

[@nitinkumar5974]

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

[@nikhil7129]

Best explanation ❤

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

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

[@srishtisuman2561]

Loved the explanation

[@guptashashwat]

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

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

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

👍

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

[@seyidaniels1350]

Awesome! First Comment

[@techdose4u]

😀

[@davissebastian4799]

vcool

[@techdose4u]

👍🏼