G-48. Number of Provinces - Disjoint Set
Vložit
- čas přidán 21. 10. 2022
- GfG-Problem Link: bit.ly/3pl2tr3
C++/Java/Codes and Notes Link: Soon
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/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
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
Understood! So fantastic explanation as always, thank you!!
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!
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 😊😊
Understood!
So fantastic explanation
Understood and thank alot for this amazing content
Thanks Striver!
understood striver thank you!!!
Hi striver really ur content is super, in similar way could u do for tress topic like binary lifting..etc
Understood thanku for creating such a good content
Thank you soo much!
you are the best🔥
understood beautifully
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
This was awesome understood
Understood 🔥🔥
Thank you .. Understood
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
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 .
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 sir!
Understood 👍
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
Hii striver.. Waiting for this.. ☺❣️
understood🔥🔥🔥
understood 👍
Understood✌️
Understood!!
Understood❤
understood!!!
Understood.
Done!
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.
understood
Understood
understood :)
Is graph series done?
great
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.
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?
Or decrease the count by 1 on successful union instead of iterating over the parent array in the last
Done
but the dfs approach was just O(V+E) , dsu is O(V^2)
Nice
idk why but this is showing me segmentation fault. can anyone help me in resolving this?
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);
🎉🎉
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
More problems on DSU also coming today ?
Yes uploaded
🐐
Understood bhaiya 🙏❤️
Understood striver
US
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 Striver
"Understood"
1st comment, mujhe 5 LAKH cash chahiye ab striver🤣🤣
us
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)
return len(set(UFObject.root))
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