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

[@imPriyansh77]

understood. Great explanations Striver bhaiya. Thank you

[@KiranKumar-sb3ti]

understood

[@DeepakKumar-cq6jm]

why do we need to seperately calculate number of extra edges in disjoint data structure while doing union when ultimate parents are same we just return so instead of returning we can just do count++ in union function

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

[@yashshukla1637]

Same!!! Striver is the best at teaching concepts for deep understanding

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

[@gautamraj-f7d]

I was thinking the same thing, but then I saw your comment. Nice observation 👏

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

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

[@avi4138]

@@VarunSharma-sk5os because to connect n nodes we must require minimum of n-1 edges (Spanning tree)

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

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

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

[@rutikbhanushali957]

The way you approach the problem is just phenomenal

[@sauravchandra10]

Once again, coded on my own. Understood clearly!

[@Piyushverse17]

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)

[@aanchaljain4610]

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

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

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

[@nimishjindal9271]

This solution blew my mind 🤯

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

[@stith_pragya]

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

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

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

[@neerajgupta9151]

bhai you're a genius! respect!

[@cinime]

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

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

[@GManiKarthik]

Are graph problems really that simple? 🤔 Or is Striver just making them look super easy? 😅 Man, what an explanation! 🤯 You're truly the GOAT of DSA! 💯🔥

[@yashshukla1637]

Note for myself: no need to watch it again. Concept is clear

[@shubhamc183]

made it super simple, thanks for your efforts ❤

[@janardhan2jordan]

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

[@yashshukla1637]

Need to do a lot of DSU questions to master the topic!!!

[@sudhanshujha9424]

jacket looks dope man🔥

[@AmanjotSingh-rj7ox]

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

[@pulkitchausali1354]

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

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@therahul5304]

Good Morning from India Bhaiya

[@takeUforward]

Yahan bhi raat k 2 baje hai bro

[@amanbhadani8840]

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

[@rameshbabuy9254]

perfect detailed 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.

[@divyachauhan363]

understood......amazinggggggg🤩🤩🤩

[@UECAshutoshKumar]

Thank you sir 🙏

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

[@sunilpanchal1498]

great explanation 🔥🔥🔥🔥

[@ShristiSethiya-ch2he]

such great explanation!!

[@kumarabhishek3890]

11:11 anyone who points to itself is a component boss, or is a ultimate parent or a component

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

[@abhaychanana7240]

Finally slight change in outfit!

[@abhishekdas8313]

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

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

[@santhosh7042]

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

[@skmirazhaque4412]

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

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

[@lakshmanchandukondreddy1720]

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

[@DeepakKumar-cq6jm]

why do we need to seperately calculate number of extra edges in disjoint data structure while doing union when ultimate parents are same we just return so instead of returning we can just do count++

[@gangsta_coder_12]

Understood 🔥🔥

[@mohakhiphop]

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

[@pulkitjain5159]

DID it my myself , maja agya

[@sukhpreetsingh5200]

Understood I solve it myself

[@divyatejaswinivengada6368]

understooood!!

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

[@KuchBhi-bs7sc]

understood bhaiya

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

[@abhishek__anand__]

Great content

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

[@kshitijmishra2716]

omg i solved this question without looking at your videos

[@arpankoley4256]

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

[@SatyamKumar-bw4vi]

Great Video..!!!

[@rimshakhan13]

Understood ✨

[@parshchoradia9909]

Understood Sir!

[@psinity]

really loved it!

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

[@suryakiran2970]

Understood❤

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

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

[@Shivanai_h]

Understood 👏

[@herculean6748]

Thanks🙌

[@Jujutsukaisen-qp7qq]

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

[@saumyaagarwal7]

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

[@reshusingh3558]

understood sir thankyou

[@1tav0]

This is great !!!!

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

[@sangammishra3670]

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

[@dharmenderkumar2841]

UNDERSTOOD

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

[@SumitKeshariMCS]

Awesome!!

[@satyamroy3783]

understood

[@abhinavbhardwaj3372]

understood sir

[@subhadeepghosh2813]

maza AAA gaya

[@ironeagle1709]

Understood!

[@piyushacharya7696]

understood man

[@RohitKumar-dy2gc]

got it bro

[@mayankaggarwal4045]

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

[@codingalley6229]

12:00 pe hai

[@hiteshnagothu887]

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

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉🎉🎉

[@adityasaxena6971]

Understood Striver

[@girikgarg8]

Done!!

[@mohammadhanif3016]

Understod

[@AmanGupta-ib5ss]

understood :)

[@ravisingh-el8np]

[@kushagramishra3026]

"understood"

[@KratosProton]

great

[@addityasharma6426]

understood :-)