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.
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!
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
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
@@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
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 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
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.
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 !!
@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
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)]
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)
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.
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; } }
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
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
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! 💯🔥
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🙏
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
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.
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.
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;
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
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()
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??
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
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 😏
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
// 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()
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
understood. Great explanations Striver bhaiya. Thank you
understood
The code also works if we just check- if(number of total edges>=n-1),then answer is NC-1
nice observation
yup, but would need a full aproach if you need to figure out which edges to replace.
@@AtulGupta-rh4if Not required. Because the question didn't specify any specific edges. It just asked how many operations
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.
The way you approach the problem is just phenomenal
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!
Bro, I have written the exact code as you have written just with the help of your previous teachings, you are a great teacher!!!!👍👍
i am not able to write myself cannot understand where i am going wrong
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
appreciate it
yes dsu stores only mst
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
@@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
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)
could you plz provide me your code for this
@@VarunSharma-sk5os sure i'll
@@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
Once again, coded on my own. Understood clearly!
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.
Will the complexities be same?
@@omop5922 yes, both have O(V+E)
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 !!
was able to do it on my own...couldn't be more thankful
@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
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)]
I am very thankful for this neat explanation
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)
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.
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;
}
}
This solution blew my mind 🤯
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
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
Understood.................Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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! 💯🔥
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🙏
Simple DFS/BFS - find number of comps based on MST formula will work as well
made it super simple, thanks for your efforts ❤
bhai you're a genius! respect!
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
Thank you sir 🙏
Understood bhaiya 🙏❤️
Understood! Supremely wonderful explanation as always, thank you very much!!
perfect detailed explanation
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.
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.
understood......amazinggggggg🤩🤩🤩
Looks like we have road in Berland problem in gfg form.Anyways awesome explanation,solved without watching the video.
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;
jacket looks dope man🔥
The total number of edges should be equal or greater than (number of node-1), then it's always possible
Other way of doing it is that return (total_no_of_edges < no_of_nodes-1) ? -1 : return no_of_compnents-1
thanks for the test case testcase itself a answer, i'm unable to think this type of test case how to do.
Solved this problem without watching the video #Thanks Striver for wonderful explanation of DisjointSet
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)
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
such great explanation!!
understood bhaiya
great explanation 🔥🔥🔥🔥
Time Complexity: O(4*alpha*no of connections). Please do correct me if I am wrong.
understood sir thankyou
Understood Sir!
Good Morning from India Bhaiya
Yahan bhi raat k 2 baje hai bro
Great content
TC - O(M(4alpha)) ---> M = edge.size()
SC - O(2V) or O(2N)
Correct me if I'm wrong
understooood!!
Great Video..!!!
UNDERSTOOD
Finally slight change in outfit!
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()
Understood I solve it myself
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??
Thanks🙌
really loved it!
Understood❤
Understood ✨
Understood 🔥🔥
understood sir
This is great !!!!
DID it my myself , maja agya
can i assume thosre extra edges are indeed cycle forming edges?
need not to count extraedges if there n-1 >total edges directly return -1
one doubt is if adjacency list is given then how to calculate extraedges
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
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
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 😏
what if edges have costs and we have to connect the components in minimum cost??
Awesome!!
got it bro
Understood!
Understood 👏
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?
understood man
Done!!
omg i solved this question without looking at your videos
Understood
maza AAA gaya
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
understood
great
Understod
understood :)
Understood Striver
"understood"
🎉🎉🎉
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..
// 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()
👏👏
understood :-)
Java code is not available and it is also not shown in video.. Please provide asap
12:00 pe hai
OG