G-48. Number of Provinces - Disjoint Set

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

[@KiranKumar-sb3ti]

understood

[@BharatiSubramanian99217]

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.

[@vishious14]

I had the very same thing in my mind

[@devanshverma8050]

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.

[@s_3095]

parents bhi kaam kr jayega!

[@devanshverma8050]

@@s_3095 it totally depends on how the code is written depending upon the problem, if u think by seeing the code that parents array will be updated before whenever u need it then yeah it would work.

[@psurya3053]

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.

[@mugambo5505]

dsa driver striver i first solved this question myself then saw explanation. it's because of you now i am confident to do questions.

[@sauravchandra10]

Thanks to you I was able to solve this on my own without watching the explanation. As always, understood clearly!

[@successsavataar.ai786]

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

[@shivamarora3554]

its a zero based indexing question dont go on example

[@potassium_cyanide_boy8515]

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

[@shivamarora3554]

One way to do this is , you can create HashSet and add the parent array elements in it. You can then return the size of sets

[@cinime]

Understood! So fantastic explanation as always, thank you!!

[@spandanbhattacharya5030]

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]

Hi I actually set and got the wrong answer. I did not understood it why it happened can u help me explain?

[@spandanbhattacharya5030]

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

[@parthivsinhvaghela6100]

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

[@stith_pragya]

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

[@free.channel715]

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 .

[@viditgupta7088]

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

[@takeUforward]

You can check the CP sheet on the tuf site for the same, thanks

[@oqant0424]

Understood! So fantastic explanation

[@AbcdEfgh-dm2pg]

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

[@vishious14]

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.

[@ast9831]

but the dfs approach was just O(V+E) , dsu is O(V^2)

[@sapna2019]

Understood thanku for creating such a good content

[@sukhpreetsingh5200]

Understood and thank alot for this amazing content

[@joshuamanivinod9873]

Thank you soo much! you are the best🔥

[@MURTHATIMAHIBABU]

Hi striver really ur content is super, in similar way could u do for tress topic like binary lifting..etc

[@sahilpanchasara]

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

[@itsaryanb9316]

It's giving me the correct answer using union By Rank

[@rajchinagundi7498]

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

[@many987]

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

[@rushidesai2836]

Thanks Striver!

[@gangsta_coder_12]

Understood 🔥🔥

[@niketgupta3884]

Hii striver.. Waiting for this.. ☺❣️

[@anshulgoel1940]

Or decrease the count by 1 on successful union instead of iterating over the parent array in the last

[@RohitKumar-dy2gc]

understood beautifully

[@ronaldo-t2d]

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?

[@prasannasippa5962]

understood striver thank you!!!

[@anshulsharma3137]

More problems on DSU also coming today ?

[@takeUforward]

Yes uploaded

[@mohdtalib7350]

Java Solution using disjoint set approach is failing the test case in gfg 119 / 121 ; Can any optimization be done in this same approach ?

[@NituPandelPCECS]

Do it by unionByRank(i, j);

[@siddharthjain3183]

isn't disjoint set template too long? During OA's i dont think we can copy paste the template and we will have to write everything from scratch and it will be too time consuming, so i think dfs would be better than disjoint set

[@1tav0]

This was awesome understood

[@shreyarawatvlogs6920]

idk why but this is showing me segmentation fault. can anyone help me in resolving this?

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@yashshukla1637]

TODO using Disjoint sets. Not for myself.

[@krishanpratap3286]

Is graph series done?

[@Chandraprakash-kx4ic]

Thank you .. Understood

[@parshchoradia9909]

Understood sir!

[@p38_amankuldeep75]

understood🔥🔥🔥

[@ACUCSPRADEEPB-up9ne]

Understood✌️

[@suryakiran2970]

Understood❤

[@saurabhkale4495]

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

[@hrushi_borhade]

Understood striver

[@krishnapalsingh3164]

1st comment, mujhe 5 LAKH cash chahiye ab striver🤣🤣

[@adityasaxena6971]

Understood Striver

[@The_Shubham_Soni]

Understood.

[@judgebot7353]

understood 👍

[@gauravghosh6562]

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.

[@anshugupta1365]

Understood!!

[@TarunKumarSaraswat]

thanks

[@shivanigupta9747]

Understood

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉🎉

[@bhavya8608]

understood!!!

[@girikgarg8]

Done!

[@kushagramishra3026]

"Understood"

[@Rajat_maurya]

understood

[@girikgarg8]

Done

[@AmanGupta-ib5ss]

understood :)

[@abhishekkunal8958]

❤

[@codingalley6229]

🐐

[@KratosProton]

great

[@himaniupadhyay8201]

US

[@addityasharma6426]

understood :-)

[@piyushraj5464]

us

[@KaushikSharma-c3q]

................

[@deepakffyt2844]

Nice

[@-VLaharika]

Understood 👍

[@TarunKumarSaraswat]

thanks

[@amanbhadani8840]

Understood

[@divyatejaswinivengada6368]

understood !!

[@prantikofficial]

understood

[@tej.askamble]

Done

[@Terminator07-x8u]

Nice

[@satyamroy3783]

understood

[@jiveshanand5948]

Understood

[@mriduljain6809]

Understood

[@itsaryanb9316]

understood

[@kaushalshinde8]

Understood

[@tanaysingh5348]

understood

[@manasranjanmahapatra3729]

Understood

[@rishabhgupta9846]

understood

[@manishpandey2725]

Understood

[@mdshohanurrahman4998]

understood

[@technologybaba192]

Understood

[@rishabhagrawal3133]

understood

[@amanxsharma]

understood

[@YATHARTHBHARDWAJ-y8m]

understood

[@YATHARTHBHARDWAJ-y8m]

understood

[@ApnaVlogs-tj7do]

understood

[@modiji8706]

understood

[@sangeetasharma8574]

understood

[@chiragbansod8252]

understood

[@ajaybind6736]

understood

[@okaynoobherenoob]

understood

[@rishabhthakur5414]

understood