G-48. Number of Provinces

G-48. Number of Provinces - Disjoint Set

Рет қаралды 70,378

Күн бұрын

GfG-Problem Link: bit.ly/3pl2tr3
C++/Java/Codes and Notes Link: Soon
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
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.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

Пікірлер: 103

@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 2 ай бұрын

understood

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

@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 10 ай бұрын

I had the very same thing in my mind

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

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

@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

@free.channel715 2 ай бұрын

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

@spandanbhattacharya5030 11 ай бұрын

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 2 ай бұрын

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

@spandanbhattacharya5030 2 ай бұрын

@@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 12 күн бұрын

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

@sauravchandra10 Жыл бұрын

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

@stith_pragya 9 ай бұрын

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

@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

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

@cinime Жыл бұрын

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

@vishious14 10 ай бұрын

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.

@anshulgoel1940 7 ай бұрын

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

@oqant0424 Жыл бұрын

Understood! So fantastic explanation

@joshuamanivinod9873 2 ай бұрын

Thank you soo much! you are the best🔥

@rushidesai2836 7 ай бұрын

Thanks Striver!

@sukhpreetsingh5200 Жыл бұрын

Understood and thank alot for this amazing content

@user-jr3dp1ss2t Жыл бұрын

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

@RohitKumar-dy2gc 11 ай бұрын

understood beautifully

@sapna2019 Жыл бұрын

Understood thanku for creating such a good content

@technologybaba192 2 ай бұрын

Understood

@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

@original_gangsta_ Жыл бұрын

Understood 🔥🔥

@rishabhthakur5414 3 ай бұрын

understood

@prasannasippa5962 Жыл бұрын

understood striver thank you!!!

@anshulsharma3137 Жыл бұрын

More problems on DSU also coming today ?

@takeUforward Жыл бұрын

Yes uploaded

@Chandraprakash-kx4ic Жыл бұрын

Thank you .. Understood

@1tav0 Жыл бұрын

This was awesome understood

@The_Shubham_Soni 11 ай бұрын

Understood.

@parshchoradia9909 Жыл бұрын

Understood sir!

@ast9831 Жыл бұрын

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

@tej.askamble 8 ай бұрын

Done

@-VLaharika Жыл бұрын

Understood 👍

@suryakiran2970 Жыл бұрын

Understood❤

@niketgupta3884 Жыл бұрын

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

@divyatejaswinivengada6368 9 ай бұрын

understood !!

@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

@judgebot7353 Жыл бұрын

understood 👍

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

@anshugupta1365 Жыл бұрын

Understood!!

@p38_amankuldeep75 Жыл бұрын

understood🔥🔥🔥

@girikgarg8 Жыл бұрын

Done!

@ronaldo-t2d 8 ай бұрын

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?

@KratosProton Жыл бұрын

great

@mohitpargaie4724 Жыл бұрын

Nice

@AmanGupta-ib5ss Жыл бұрын

understood :)

@hrushi_borhade Жыл бұрын

Understood striver

@abhishekkunal8958 4 күн бұрын

❤

@himaniupadhyay8201 Жыл бұрын

@pratyakshhhhhhhhhhhhhhhhhhhhh 8 ай бұрын

🎉🎉

@shreyarawatvlogs6920 7 ай бұрын

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

@krishanpratap3286 Жыл бұрын

Is graph series done?

@adityasaxena6971 Жыл бұрын

Understood Striver

@addityasharma6426 Жыл бұрын

understood :-)

@udaytewary3809 Жыл бұрын

Understood bhaiya 🙏❤️

@gauravghosh6562 2 ай бұрын

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.

@kushagramishra3026 Жыл бұрын

"Understood"

@codingalley6229 Жыл бұрын

🐐

@krishnapalsingh3164 Жыл бұрын

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

@piyushraj5464 3 ай бұрын

@user-up6sl2gq8p 24 күн бұрын

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

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