G-49. Number of Operations to Make Network Connected - DSU

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too,. Do follow me on Instagram: striver_79

[@priyanshkumar17]

understood. Great explanations Striver bhaiya. Thank you

[@KiranKumar-sb3ti]

understood

[@tanujaSangwan]

Unbelievable! I managed to solve this question within 5-6 minutes without needing to watch any videos or seek help. All test cases passed successfully. It’s rare for me to get the intuition for graph problems so quickly, but I think I’ve really improved over time. The concept of (n-1) edges MST concept and the idea of using number of provinces clicked right away. It’s fascinating how things come together.

[@sachindramishra2813]

The code also works if we just check- if(number of total edges>=n-1),then answer is NC-1

[@rishabhranjan5162]

nice observation

[@AtulGupta-rh4if]

yup, but would need a full aproach if you need to figure out which edges to replace.

[@manideepaktelaprolu3073]

@@AtulGupta-rh4if Not required. Because the question didn't specify any specific edges. It just asked how many operations

[@prantikofficial]

To be honest the most easiest explanation of the problem also reusing the same code snippet and using it every time is the best thing, thanks for such huge tips!

[@ayushanand6957]

Bro, I have written the exact code as you have written just with the help of your previous teachings, you are a great teacher!!!!👍👍

[@mohdkhaleeq7468]

i am not able to write myself cannot understand where i am going wrong

[@CodeWithKush]

We can ignore dealing with the number of extra edges, instead, put this condition on the top - int m = edges.length; if(m < n-1) return -1; // If the number of edges is less than no. of nodes - 1, then it is not possible to construct a connected graph, right. Just as simple as that. (Check with examples)

[@VarunSharma-sk5os]

could you plz provide me your code for this

[@abdulkareem_275]

​@@VarunSharma-sk5os sure i'll

[@kapildeshmukh7878]

@@VarunSharma-sk5os class Solution { public: int Solve(int n, vector& edges) { int m = edges.size(); // Corner case where there is not enough minimum supply of edges // to connect all the nodes together. (minimum n-1 edges needed) if(m < n-1) { return -1; } // Init DisjointSet DisjointSet ds(n); for(auto edge : edges){ ds.unionBySize(edge[0],edge[1]); } // count up number of components // Which equal to No of ultimate self parents int cnt = 0; for(int i=0; i

[@rutikbhanushali957]

The way you approach the problem is just phenomenal

[@Rajat_maurya]

Note for me: 1) DSU extra edge of same component ko ignore karta hai 2) DSU minimum edge ka connected graph hota hai ( for visualization ) 3) component of graph ki bat ho rahi think of DSU once class Solution { private: int findPar(int node,vector &parent) { if(node==parent[node]) return node; return parent[node]=findPar(parent[node],parent); } public: int makeConnected(int n, vector& connections) { int totalEdge=connections.size(); if(totalEdge

[@divyanshsrivastava7150]

appreciate it

[@pulkitjain5159]

yes dsu stores only mst

[@anupn5945]

Bhai dsu sirf mst nahi store karta Jo bhi edges pehle input me diye jate hai wo unko connect karta hai Agar dsu se mst banana hai toh based on weight sort karke dsu apply karna padega

[@pulkitjain5159]

@@anupn5945 ya bro sorry , par jab undirected graph hoga jinka wieght same hoga toh woh mst hi ban jayega crux yahi tha kehne ka bus ki dsu kewal n-1 edges store karega

[@sauravchandra10]

Once again, coded on my own. Understood clearly!

[@arjunprasad1071]

I was following the graph series ; the previous problem being Number of Provinces. I was able to apply DSU to it. However, I kept getting wrong answer to this problem. Dejected, I started your video and at 3:21 I suddenly realised the mistake I was doing with my approach ( my mistake being that, to connect 'n' components you need just 'n-1' wires) ; I was able to submit instantly then. Thanks for the wonderful, intuitive explainer !!

[@aanchaljain4610]

was able to do it on my own...couldn't be more thankful

[@harshitpandey7521]

One small request. It would be great if you can quickly cover in your video, how these DSU problems can also be solved by dfs/bfs! For example, in this one, finding connected components and number of redundant edges through dfs is possible(below is the formula). But I am not sure how to go about finding which are the extra edges using dfs/bfs. Any inputs on that would be great! Redundant edges = Total edges - [(Number of Nodes - 1) - (Number of components - 1)]

[@pulkitchausali1354]

@take U forward little observation of spanning tree concept we can just compare if given edges i:e edges.length < n-1(edges required to construct a spanning tree with n edges) return -1 else return numberOfComponents -1

[@goramnikitha5491]

I am very thankful for this neat explanation

[@PiyushKumar-mn3uh]

We can also solve this problem by using DFS/bfs 1. Count the number of components using bfs/DFS 2. To make a graph connected, we have required at least n-1 edges. If given edges >= n-1 edeges then we can connect the components otherwise we can't. 3. If possible return total components - 1 or if not possible simply return -1.

[@omop5922]

Will the complexities be same?

[@mayankgera7055]

@@omop5922 yes, both have O(V+E)

[@piyushtyagi2131]

Great Explanation !!! Actually we don't have to traverse again to count the no of connected components using the parent array. Let numComponent=n (total num of vertices) initially if parent(u)!=parent(v) we can just do numComponent-- because that node would be a part of some group at the end we get the no of connected component. int numComponent=n,canRem=0; for(int i=0;i

[@stith_pragya]

Understood.................Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@nimishjindal9271]

This solution blew my mind 🤯

[@ManishKumar-zk5ky]

Es question me bina extraEdges nikal ke bhi bana sakte hai ham check karenge ki if(edges.size()< n-1) return -1 kyoki n vertices ko connect karne ke liye n-1 edges to chahiye hi chahiye uske baad sirf connected components nikal kar one minus kar denge wahi answer hoga and Thanks for such a nice explanation🙏

[@Chandraprakash-kx4ic]

Another trick to get "No. of extra edges" No. of extra edges = Total no. of edges - (least no. of edges we need to make a connected graph) No. of extra edges = edge.size() - (n-1)

[@AquaRegia-i3u]

We have to have to find n for each component. We cannot use the n of overall graph. Consider, n=4 and edges as (0,1) , (0,2), (1,2). Now extra edges = 3 - (4-1) = 0, means there is no extra edge. But we need one edge to connect to vertex 3. Hence n is not total nodes in graph, it is total nodes in component. So extra edges will be = 3 - (3-1) - (1-1) = 1. Now we got required extra edge.

[@Amansinghal321]

Yes, you are right, following is the working code: class Solution { public int makeConnected(int n, int[][] connections) { DisjointSet set = new DisjointSet(n); int conCom = n; for (int[] con : connections) { int from = con[0]; int to = con[1]; if (set.union(from, to)) conCom--; } if (connections.length >= n-1) return conCom - 1; else return -1; } } class DisjointSet{ private Map parent; private Map rank; public DisjointSet(int n) { parent = new HashMap(); rank = new HashMap(); } public int find(int k) { if (parent.get(k) != k) { parent.put(k, find(parent.get(k))); } return parent.get(k); } private void add(int a) { if (parent.get(a) == null) { parent.put(a, a); rank.put(a, 0); } } public boolean union(int a, int b) { add(a); add(b); int x = find(a); int y = find(b); if (x == y) return false; if (rank.get(x) < rank.get(y)) { parent.put(x, y); } else if (rank.get(x) > rank.get(y)) { parent.put(y, x); } else { parent.put(x, y); rank.put(y, rank.get(y) + 1); } return true; } }

[@AdityaKumar-be7hx]

Watching this again after 6 months to revise and just found two small optimizations we can do. 1. If we have a graph of V nodes and we want to connect the nodes then we need at least V-1 nodes. With that, instead of checking extraEdges>=ans, we can just do this at the start: if(edges

[@shubhamc183]

made it super simple, thanks for your efforts ❤

[@neerajgupta9151]

bhai you're a genius! respect!

[@cinime]

Understood! Supremely wonderful explanation as always, thank you very much!!

[@UECAshutoshKumar]

Thank you sir 🙏

[@divyachauhan363]

understood......amazinggggggg🤩🤩🤩

[@sudhanshujha9424]

jacket looks dope man🔥

[@AmanjotSingh-rj7ox]

Simple DFS/BFS - find number of comps based on MST formula will work as well

[@amanbhadani8840]

Looks like we have road in Berland problem in gfg form.Anyways awesome explanation,solved without watching the video.

[@rameshbabuy9254]

perfect detailed explanation

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@vaibhavagarwal1479]

A little different approach on Disjoint Set only int Solve(int n, vector& edge) { // code here if(n-1 > edge.size())return -1; dj d1(n); for(int i = 0;i

[@ShristiSethiya-ch2he]

such great explanation!!

[@anshulkumarneekhara9377]

It works even if we just check the relation between no_of_edges ( edge.size() ) and no_of_nodes ( n ). if( edge.size() >= n-1 ) return NC - 1 ; return -1 ; NC is no. of connected components. but yeah we are doing it using Disjoint Set so increasing the count of extra edge by checking their parents equal looks good.

[@netviz8673]

Strivers way was to use DSU. And in that we get to know the ultimate parent node of each node and hence just by simply using the edges array like theres no need to go for the creation of adjacency list and you can simply by making use of the edges array can get to know if there is an already existing connection between two nodes which can be deduced by checking both of their ultimate parent nodes. If they are same that means they are already connected and the current edge is redundant hence store it in the extras. And if the edge is connecting two nodes for the first time both will have different parent node value and then they will be connected using either UnionBySize() or UnionByRank() functions and after they get connected the joining node will have its ultimate parent node updated to be same as the other one. Also to determine the number of components simply count the number of nodes having parent node equal to themselves after the graph has been created.

[@pulkitchausali1354]

Solved this problem without watching the video #Thanks Striver for wonderful explanation of DisjointSet

[@divyatejaswinivengada6368]

understooood!!

[@sunilpanchal1498]

great explanation 🔥🔥🔥🔥

[@therahul5304]

Good Morning from India Bhaiya

[@takeUforward]

Yahan bhi raat k 2 baje hai bro

[@abhishek__anand__]

Great content

[@gautamsaxena4647]

understood bhaiya

[@SatyamKumar-bw4vi]

Great Video..!!!

[@santhosh7042]

thanks for the test case testcase itself a answer, i'm unable to think this type of test case how to do.

[@reshusingh3558]

understood sir thankyou

[@skmirazhaque4412]

Time Complexity: O(4*alpha*no of connections). Please do correct me if I am wrong.

[@abhaychanana7240]

Finally slight change in outfit!

[@mohakhiphop]

TC - O(M(4alpha)) ---> M = edge.size() SC - O(2V) or O(2N) Correct me if I'm wrong

[@rajatsaraf237]

Did it by my own but there is 1 small modification, we don't need to calculate extra edges. We can simply check if no of edges present is < no of vertices - 1 (Since minimum no of edges requires to connect n vertices is n-1) then, we can return -1 as it is not possible to connect all vertices. rest we can return noOfComponents - 1; int edgeCount = edge.length; if(edgeCount < n - 1) return -1;

[@psinity]

really loved it!

[@sukhpreetsingh5200]

Understood I solve it myself

[@r_uhi05]

Understood!

[@suryakiran2970]

Understood❤

[@abhishekdas8313]

The total number of edges should be equal or greater than (number of node-1), then it's always possible

[@pulkitjain5159]

DID it my myself , maja agya

[@parshchoradia9909]

Understood Sir!

[@1tav0]

This is great !!!!

[@dharmenderkumar2841]

UNDERSTOOD

[@SandeepSingh-xs1bt]

Finally A black jacket, but still red color T shirt XD, In your entire DP series you wore red color hoodie and in the graph Series you wear red color T-shirt in every Video, anything Special about red color ,Striver Sir 😏

[@herculean6748]

Thanks🙌

[@original_gangsta_]

Understood 🔥🔥

[@lakshmanchandukondreddy1720]

Other way of doing it is that return (total_no_of_edges < no_of_nodes-1) ? -1 : return no_of_compnents-1

[@visheshagrawal8676]

okay i understood that he wants us to understand the concept of dsu , but extra edges can be found like that also edges.size() - V , these will be extra edges , according to me.......... and code without disjoint if someone was thinking using dfs //{ Driver Code Starts #include using namespace std; // } Driver Code Ends // User function Template for C++ class Solution { public: void dfs( vector adj[] , vector &vis, int ind){ vis[ind] = true; for( auto it : adj[ind]){ if( !vis[it]){ dfs(adj,vis,it); } } } int Solve(int n, vector& edge) { if( n - 1 > edge.size() ) return -1; vector vis(n,false); vector adj[n]; for( auto it : edge){ adj[it[0]].push_back(it[1]); adj[it[1]].push_back(it[0]); } int count = 0; for( int i = 0 ; i < n ;i++){ if( !vis[i]){ count++; dfs(adj,vis,i); } } return count - 1; } }; //{ Driver Code Starts. int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; vector adj; for (int i = 0; i < m; ++i) { vector temp; for (int j = 0; j < 2; ++j) { int x; cin >> x; temp.push_back(x); } adj.push_back(temp); } Solution Obj; cout

[@abhinavbhardwaj3372]

understood sir

[@ksankethkumar7223]

add a base case if no of edges is less than n-1, then return -1 else directly at the end return (no. of comp - 1)

[@rimshakhan13]

Understood ✨

[@The_Shubham_Soni]

Understood.

[@SumitKeshariMCS]

Awesome!!

[@RohitKumar-dy2gc]

got it bro

[@Shivanai_h]

Understood 👏

[@lakshsinghania]

first i was scared to solve this question but then applied the prev knowledge of DSU i solved on my own , thnk u striver //{ Driver Code Starts #include using namespace std; // } Driver Code Ends // User function Template for C++ // mk the class disjointset class DisjointSet { vector rank, parent, size; public: // mk the parameterised constructor to put in the data DisjointSet(int n) { rank.resize(n + 1, 0); parent.resize(n + 1); size.resize(n + 1); for (int i = 0; i n >> m; vector adj; for (int i = 0; i < m; ++i) { vector temp; for (int j = 0; j < 2; ++j) { int x; cin >> x; temp.push_back(x); } adj.push_back(temp); } Solution Obj; cout

[@manasranjanmahapatra3729]

Understood

[@jitendrakumar-vv8ho]

will i be allowed to use global variables and global functions in interview ?? I am used to it and not comfortable in using oops concepts of classes and objects??

[@girikgarg8]

Done!!

[@kshitijmishra2716]

omg i solved this question without looking at your videos

[@rishabhthakur5414]

understood

[@anand_patel_91]

I guess this solution would also work just fine... if the number of edges are less than n-1, then the graph cannot be connected... then just calculate all the connected componenets (ct) and then we can caonnect all those toghether using ct-1 edges... int Solve(int n, vector& edges) { if(edges.size()

[@piyushacharya7696]

understood man

[@gondshubhamsurendra6642]

hey striver in your line no 65 in gfg where the condition is ds.findPar(x)==ds.findPar(y) I have written ds.parent[x]==ds.parent[y] I was getting wrong answer .Can you suggest what would be the possible reason ??.I think that at that time may be time path was not compressed

[@SiddhantGupta-j8h]

[@arpankoley4256]

can i assume thosre extra edges are indeed cycle forming edges?

[@KratosProton]

great

[@AmanGupta-ib5ss]

understood :)

[@subhadeepghosh2813]

maza AAA gaya

[@Kartik-xq4mu]

Just a correction instead of parenti==i go for findupari==i while councting or else if last edge connects 2 components answer will be wrong

[@mohammadhanif3016]

Understod

[@sangammishra3670]

need not to count extraedges if there n-1 >total edges directly return -1

[@saumyaagarwal7]

one doubt is if adjacency list is given then how to calculate extraedges

[@addityasharma6426]

understood :-)

[@Jujutsukaisen-qp7qq]

what if edges have costs and we have to connect the components in minimum cost??

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉🎉🎉

[@pranjulmishra1017]

// can be solved using dfs void dfs(int node, vectoradj[], vector &vis){ vis[node]=1; for(auto it : adj[node]){ if(!vis[it]){ dfs(it,adj,vis); } } } int Solve(int n, vector& edge) { // code here if(edge.size()

[@amitp277]

👏👏

[@kushagramishra3026]

"understood"

[@PulkitAgg13]

Bhaiya aap to hume karva dete ho ye sab lekin aapke time mai aap khud kese sochte the ye sab...Tab to itne resources bhi nahi the..

[@adityamangla4794]

If we use parent array instead of findParent in the first loop, it's not working...However in the second loop, either works. Can anyone clarify this?

[@adityasaxena6971]

Understood Striver

[@mayankaggarwal4045]

Java code is not available and it is also not shown in video.. Please provide asap

[@codingalley6229]

12:00 pe hai

[@diveshrajput572]

OG

[@karanveersingh8102]

bhi angrazi ka coda banna zaruri h kya, hindi me nahi bataya zayta!!

[@coding8000]

Understoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood