i would advice not to use parent array for finding parent cuz in some cases it doesn't have correct parent values being updated (for eg in accounts merge question), also findpar function will always give correct results without any extra complexity cuz if the parent of particular node is already updated it will always fall in base case resulting in O(1) operation.
There's also another way to do this. We can keep the count of components initially as n within the DSU class (as a member variable). That is each vertex is a component by itself. Every time we do a union between u and v, we can reduce the number of components by 1. Finally we can simply return this value.
In this problem if we have 1 based indexing then why we are using for loop from 0 to n-1 , because for 1 based indexing ideally we should use for loop from 1 to n, and also the code of for loop from 0 to n-1 is working fine ... How?? I was initially stucked but after looking and analysing the code I understood : Here is how ? in the union by size function we are actually making union for zero based indexing of the array so here are two ways => 1. ds.unionBySize(i,j); and run for loop from 0 to n-1 || zero based indexing 2. ds.unionBySize(i+1,j+1); and run for loop from 1 to n || one based indexing I hope this will help someone || Happy coding 😊😊
thank you, sir, I am self-preparing for my placements, your lectures are useful for most of us. Great teaching skills. i have watched entire graph series, and dp series.
we can also use a variable num = V and every time we do a union(u,v)we can do n - - ; int he union function only that way we don't have to run it extra loop to check for the count .
i think rather than making parent array object as public, we can create one getter method that will just return us element at particulat index like this: int getParentEleme(int idx) const{ if(idx < 0 || idx > n){ throw std::invalid_argument( "illegal index value" ); } return parent[idx]; } Or overload [] operator for DisjointSet class
hey striver great series.. thanks for the amazing content... Just one request meanwhile can you also share some of the codeforces questions based on graphs based on what we've learnt till now? It'll be really helpful
Thank You for the amazing explanation Striver bhaiya! I judt had an observation that in the final loop where we are counting the number of par[i]=i, there if the count comes out to be 3, it doesn't mean that if we output the parent array in the end, it would not have only 3 distinct elements. It may have more, as the path compression updates only the ultimate parent. So, those who put the parent array into a set and outputted its size, they will get a wrong answer in some cases. Therefore, the condition which checks whether someone is an ultimate parent is if par[i]=i, otherwise it may cause errors in implementation (not logical error).
@@tusharmittal3959 Logically, the set contains all the super parents, so if we output the size of the set, it should give the number of disjoint sets. That would be true in this case too, if after path compression we updated the parents of each node after each compression. But we don't do that to save time. Thus, let's say 1 is the parent of 2 and 3, so number of parents currently =1. But now let's say 4 comes and 4 becomes the parent of 1, so logically, the parent of 1,2,3,4, all are 4. But, since we only update the case for 1. 2,3 still have 1 as their parent in the parent set. So, now if we count in the set, we will find 4,1 as 2 parents. Thus to avoid that, we use the rule par[i] = i, then only it's a super parent rule to determine number of parents.
@@spandanbhattacharya5030 but if 4 comes then size of 4 will be less than size of 1 so 4 is not going to be the parent of 1 since we always append small portion into big...
Using a size array is not necessary because we dont really care about the size. We just want to see if their parents are same, if their parents are not then make one of them the parent of another. This is a little space optimization one could make.
When you are converting adjacency matrix to list, it should be adjLs[i+1].push_back(j+1) as the nodes are 1 based indexed so, doing adjLs[i].push_back[j] for row 0 say for example would mean there is edge between any node 'x' and node 0 which is false as node 0 doesn't exist
Hey striver, in this problem i tried using unionByRank in GFG but it is giving wrong answer. So, we should always use UnionBySize or it has some problem with GFG?? Thank you
It does give wrong answer, you have to fix the adjacency matrix indexes, as the node starts from 1, so its 1 based indexing, this will fix your issue, I dont know how strive passed the above test cases, maybe during that time it was zero based indexing. DisjointSet ds(V); int n=adj.size(); int m=adj[0].size(); int id = 1; for(int i=0;i
Solution of this video is here. class DisjointSet { public: vector parent, size; DisjointSet(int n) { parent.resize(n + 1); size.resize(n + 1, 1); for (int i = 0; i
hello bhaiya, i have a better approach than this, where we have a variable named "components" with an initial value as the number of vertices, we traverse through the adjacent matrix and wherever we see a edge, if the parent of both the nodes involved in the edge are not equal then we combine them by taking union but also decrement the components variabele count by 1 as we are combining two different components into one.By this at the end of our V*V iteration we will have the number of components and simply return it instead of initiating another loop to check if the parent of a node is itself.
Python code for union find and Number of province #User function Template for python3 class UnionFind: # Constructor def __init__(self, n_cities): self.root = [i for i in range(n_cities)] # tells the root node for each node, initially itself self.rank = [1]*n_cities # rank/height of each node def find(self, x): # find the root of a node x if self.root[x] == x: return x self.root[x] = self.find(self.root[x]) return self.root[x] def union(self, x, y): rootx = self.find(x) rooty = self.find(y) if rootx!=rooty: # Check for rank of rootx and rooty. Attach smaller rank graph to larger rank if self.rank[rootx] > self.rank[rooty]: self.root[rooty] = rootx elif self.rank[rooty] > self.rank[rootx]: self.root[rootx] = rooty else: # the ranks of rootx and rooty are the same self.root[rooty] = rootx self.rank[rootx]+=1 def connected(self, x, y): # Check wheather 2 nodes are connected or not return self.find(x) == self.find(y)
class Solution: def numProvinces(self, adj, V): UFObject = UnionFind(V) for i in range(len(adj)): for j in range(len(adj)): if i!=j and adj[i][j] == 1: UFObject.union(i, j)
#make sure that all nodes have the root as the ultimate parent for i in range(V): UFObject.root[i] = UFObject.find(i)
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
i would advice not to use parent array for finding parent cuz in some cases it doesn't have correct parent values being updated (for eg in accounts merge question), also findpar function will always give correct results without any extra complexity cuz if the parent of particular node is already updated it will always fall in base case resulting in O(1) operation.
There's also another way to do this. We can keep the count of components initially as n within the DSU class (as a member variable). That is each vertex is a component by itself. Every time we do a union between u and v, we can reduce the number of components by 1.
Finally we can simply return this value.
I had the very same thing in my mind
In this problem if we have 1 based indexing then why we are using for loop from 0 to n-1 , because for 1 based indexing ideally we should use for loop from 1 to n, and also the code of for loop from 0 to n-1 is working fine ... How??
I was initially stucked but after looking and analysing the code I understood : Here is how ?
in the union by size function we are actually making union for zero based indexing of the array
so here are two ways =>
1. ds.unionBySize(i,j); and run for loop from 0 to n-1 || zero based indexing
2. ds.unionBySize(i+1,j+1); and run for loop from 1 to n || one based indexing
I hope this will help someone || Happy coding 😊😊
thank you, sir, I am self-preparing for my placements, your lectures are useful for most of us. Great teaching skills. i have watched entire graph series, and dp series.
dsa driver striver i first solved this question myself then saw explanation. it's because of you now i am confident to do questions.
Thanks to you I was able to solve this on my own without watching the explanation. As always, understood clearly!
we can also use a variable num = V and every time we do a union(u,v)we can do n - - ; int he union function only that way we don't have to run it extra loop to check for the count .
i think rather than making parent array object as public, we can create one getter method that will just return us element at particulat index like this:
int getParentEleme(int idx) const{
if(idx < 0 || idx > n){
throw std::invalid_argument( "illegal index value" );
}
return parent[idx];
}
Or overload [] operator for DisjointSet class
hey striver great series.. thanks for the amazing content... Just one request meanwhile can you also share some of the codeforces questions based on graphs based on what we've learnt till now? It'll be really helpful
You can check the CP sheet on the tuf site for the same, thanks
Thank You for the amazing explanation Striver bhaiya!
I judt had an observation that in the final loop where we are counting the number of par[i]=i, there if the count comes out to be 3, it doesn't mean that if we output the parent array in the end, it would not have only 3 distinct elements.
It may have more, as the path compression updates only the ultimate parent. So, those who put the parent array into a set and outputted its size, they will get a wrong answer in some cases.
Therefore, the condition which checks whether someone is an ultimate parent is if par[i]=i, otherwise it may cause errors in implementation (not logical error).
Hi I actually set and got the wrong answer. I did not understood it why it happened can u help me explain?
@@tusharmittal3959 Logically, the set contains all the super parents, so if we output the size of the set, it should give the number of disjoint sets.
That would be true in this case too, if after path compression we updated the parents of each node after each compression. But we don't do that to save time.
Thus, let's say 1 is the parent of 2 and 3, so number of parents currently =1.
But now let's say 4 comes and 4 becomes the parent of 1, so logically, the parent of 1,2,3,4, all are 4. But, since we only update the case for 1. 2,3 still have 1 as their parent in the parent set.
So, now if we count in the set, we will find 4,1 as 2 parents.
Thus to avoid that, we use the rule par[i] = i, then only it's a super parent rule to determine number of parents.
@@spandanbhattacharya5030 but if 4 comes then size of 4 will be less than size of 1 so 4 is not going to be the parent of 1 since we always append small portion into big...
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Using a size array is not necessary because we dont really care about the size. We just want to see if their parents are same, if their parents are not then make one of them the parent of another. This is a little space optimization one could make.
When you are converting adjacency matrix to list, it should be adjLs[i+1].push_back(j+1) as the nodes are 1 based indexed so, doing adjLs[i].push_back[j] for row 0 say for example would mean there is edge between any node 'x' and node 0 which is false as node 0 doesn't exist
Understood! So fantastic explanation as always, thank you!!
Hi striver really ur content is super, in similar way could u do for tress topic like binary lifting..etc
Understood!
So fantastic explanation
Or decrease the count by 1 on successful union instead of iterating over the parent array in the last
understood beautifully
Understood and thank alot for this amazing content
Thanks Striver!
but the dfs approach was just O(V+E) , dsu is O(V^2)
Understood thanku for creating such a good content
Thank you soo much!
you are the best🔥
thanks
Understood 🔥🔥
understood striver thank you!!!
More problems on DSU also coming today ?
Yes uploaded
Hey striver, in this problem i tried using unionByRank in GFG but it is giving wrong answer. So, we should always use UnionBySize or it has some problem with GFG??
Thank you
It's giving me the correct answer using union By Rank
It does give wrong answer, you have to fix the adjacency matrix indexes, as the node starts from 1, so its 1 based indexing, this will fix your issue, I dont know how strive passed the above test cases, maybe during that time it was zero based indexing.
DisjointSet ds(V);
int n=adj.size();
int m=adj[0].size();
int id = 1;
for(int i=0;i
if we make a set and then store all of it parent element in it and returning the size of set then why is it giving wrong answer?
Thank you .. Understood
This was awesome understood
Understood
Understood.
Understood striver
Understood sir!
understood
Hii striver.. Waiting for this.. ☺❣️
Understood 👍
Java Solution using disjoint set approach is failing the test case in gfg 119 / 121 ; Can any optimization be done in this same approach ?
Do it by unionByRank(i, j);
Is graph series done?
Understood❤
understood !!
Done!
Understood Striver
Done
Understood!!
idk why but this is showing me segmentation fault. can anyone help me in resolving this?
understood 👍
understood🔥🔥🔥
Solution of this video is here.
class DisjointSet {
public:
vector parent, size;
DisjointSet(int n) {
parent.resize(n + 1);
size.resize(n + 1, 1);
for (int i = 0; i
Understood bhaiya 🙏❤️
great
US
Nice
understood :)
🎉🎉
"Understood"
❤
hello bhaiya, i have a better approach than this, where we have a variable named "components" with an initial value as the number of vertices, we traverse through the adjacent matrix and wherever we see a edge, if the parent of both the nodes involved in the edge are not equal then we combine them by taking union but also decrement the components variabele count by 1 as we are combining two different components into one.By this at the end of our V*V iteration we will have the number of components and simply return it instead of initiating another loop to check if the parent of a node is itself.
🐐
1st comment, mujhe 5 LAKH cash chahiye ab striver🤣🤣
understood :-)
us
................
Python code for union find and Number of province
#User function Template for python3
class UnionFind:
# Constructor
def __init__(self, n_cities):
self.root = [i for i in range(n_cities)] # tells the root node for each node, initially itself
self.rank = [1]*n_cities # rank/height of each node
def find(self, x):
# find the root of a node x
if self.root[x] == x:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx!=rooty:
# Check for rank of rootx and rooty. Attach smaller rank graph to larger rank
if self.rank[rootx] > self.rank[rooty]:
self.root[rooty] = rootx
elif self.rank[rooty] > self.rank[rootx]:
self.root[rootx] = rooty
else: # the ranks of rootx and rooty are the same
self.root[rooty] = rootx
self.rank[rootx]+=1
def connected(self, x, y):
# Check wheather 2 nodes are connected or not
return self.find(x) == self.find(y)
class Solution:
def numProvinces(self, adj, V):
UFObject = UnionFind(V)
for i in range(len(adj)):
for j in range(len(adj)):
if i!=j and adj[i][j] == 1:
UFObject.union(i, j)
#make sure that all nodes have the root as the ultimate parent
for i in range(V):
UFObject.root[i] = UFObject.find(i)
return len(set(UFObject.root))
thanks
Understood
understood
Understood✌️
understood!!!
Done
Nice
Understood
Understood
Understood
understood
understood
understood
understood
understood
understood
understood
understood
understood
Understood
Understood
understood
Understood
understood
understood
understood
understood
understood
understood