G-7. Number of Provinces | C++ | Java | Connected Components

GfG-Problem Link: bit.ly/3yR3dIB
C++/Java/Codes and Notes Link: takeuforward.o...
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...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Do follow me on Instagram: striver_79

[@shubhamshukla4215]

Hey Striver, I am just wondering is there any need adding adjLs[i].push_back(j); adjLs[j].push_back(i); I think adjLs[i].push_back(j) will get the job done, because adj Matrix will store the information whether it's two way connection or one way.

[@kunalbandooni4009]

Striver: Hey Everyone.. Me: *likes the video* Context: Belief in the content I am going to learn. Learning a lot!!

[@alt-f4gaming222]

why are we writing the dfs code in the private, can anyone pls explain the difference in writing the function in private and public

[@apexgamer1288]

​@@shubhamshukla4215a😊😊

[@AnkitGupta-tp3ln]

I really like the Neon red light of your pen, and how it stays for few seconds before it goes away so that it don't clutter. That's so amazing.

[@yashrawat5158]

its a glitter feature in an app. which stays for few seconds and then disappears .

[@divyanksharma236]

naye naye lagte ho

[@srirambharadwaj1937]

It’s on goodnotes for ipad.

[@satendra6200]

😅@@divyanksharma236

[@rishabhranjan5162]

It's a Goodnotes 5 feature on ipad

[@user-ti3bd8mp1w]

In the code to convert adjacency matrix to adjacency list: striver mentioned 2 lines : adj[i].push_back(j); //1 adj[j].push_back(i); //2 I think it should only have first otherwise there would be repetitions...it works in code bcz visited handles repetitions

[@alexwhitewood6480]

This only works bcz we're going through all the nodes in the outer loop anyways

[@srijangupta4680]

seen this comment after wasting my whole day🥺

[@xyz1869]

correct 👍👍

[@tsk1217]

You are right

[@toobasedfortheworld]

Hey why it is given i!=j in convertion of matrix to list?

[@Sachinraj_143-king]

No i think time complexity of this question is O(n^2). because one loop is travel for all vertices and in each one loop a inner loop is also created .here not O(n)+O(v+2E) .I think here T.C. is O(n)*O(v+2e) which is approximately equal to O(n^2)

[@vaibhavthalanki7320]

no

[@kapilsingh2816]

4:39 the loop is for (int i = 1; i

[@sooyashjaju4208]

Actually kapil, the diagram Given is based on 1 indexing but the solution which it is accepting is 0 based, I faced same issue and eventually made 5 wrong submission 😄

[@tusharvlogs6333]

@@sooyashjaju4208 bhaiiii gladd i came here to see this comment. wasted my 1 hr . thankyou for answering this

[@VishalPatel_imvishal]

+1 underrated comment

[@Virtualexist]

@@sooyashjaju4208Thanks man! I wasted a lot of time thinking about it. Diagram and test cases should be in sync. 😢 But yea thanks!!!

[@Virtualexist]

Thanks for asking!

[@kausachan4167]

nice explanation striver bhai, one doubt is that should we need to do adj[i].push(j) and adj[j].push(i) both? I think one is enough bcoz anyway we're traversing the matrix completely and it is an undirected graph so edge will be marked in both matrix[i][j] and matrix[j][i], if we push it twice we will have duplicate elements in array list which is not a problem but still can be avoided. crct me if im wrong.

[@100anvay5]

i am also thinking about this. yes it will work

[@NARENDRAPAL-zh6fk]

Yes, it will work

[@varunaggarwal7126]

nice catch

[@AbhishekVerma-yw1ps]

Rudrashish

[@yoshitaratnawat8425]

In adjacency list representation of unordered graph we need to update the edge for both the vertices that's why we've pushed both

[@startercoder]

really impressive content , even now I am tired but your confidence give me confidence to learn

[@abdalla4425]

Perfect. Solved it with martix intially but found it easier to solve after converting adjacency list

[@vatsaljain662]

bhaiya that O(N) should be O(V) basically coz v is total number of vertices and O(N) is what we used to use previously (in arrays , linked list , trees and else where ) , right ??

[@RAHULMAHESHWARIdexter]

My Approach using BFS (same time complexity) Intuition is that everytime our queue gets empty, we have traversed all connected component to that node. Solved it before watching the video, thought about using dfs also, solved it and watched the video and I am happy that I was able to think exact same dfs solution. class Solution { public: int findCircleNum(vector& isConnected) { int provinces = 0; queue q; int n = isConnected.size(); vector vis(n,0); for(int i=0;i

[@tejasc7409]

Bhaiya ! You can add a node to adjacency list only once . adj.get(i).add(j) is enough , not vice versa . It runs fine

[@sushyyyyyyyy]

only once is for directed graphs & vice-versa is for undirected!

[@tejasc7409]

@@sushyyyyyyyy not in this case. As it has been given in Adjacency matrix. So it will be one if there is an edge.

[@sushyyyyyyyy]

@@tejasc7409 no the graph is given undirected! Means two edges from u-> v & v->u like a[u][v] & a[v][u]

[@chiragpassi1832]

@@sushyyyyyyyy yeah , but in matrix for i-j and j-i both have 1 , so it will added anyone

[@tejasc7409]

@@chiragpassi1832 exactly

[@ramanpareek5218]

liked the video, notes taken, understood

[@anubhavpabby6856]

Hi striver bhaiya instead of converting adjList to adjMatrix we could also perform dfs directly on adjMatrix and get the answer. Because it could help us to reduce the space complexity. Code for dfs on adjMatrix : void dfs(int src, vector& adj, vector& visited) { visited[src] = true; for(int i=0; i

[@adityajasood4891]

Yes , I want to ask leetcode and gfg practice both are same right? Input is adj matrix. Only difference in gfg ArrayList and in leetcode int[][] .

[@ajaysarkate6624]

@@adityajasood4891 In java code, there is already a list given, then we are taking new list in our code?

[@jitinroy2246]

@@ajaysarkate6624 already given list consist of matrix, so we are converting that from matrix to value type arraylist.

[@musaveermanekia4035]

What's wrong here it shows time limit exceeded at some point void callDfs(vector&vis, vectoradj, int ind){ vis[ind] = true; for(int j = 0; j < adj[ind].size() ; j++){ if(adj[ind][j] == 1 && vis[j] == false){ callDfs(vis, adj, j); } } } int numProvinces(vector adj, int V) { vectorvis(V, false); int ans = 0; for(int i = 0; i < V; i++){ if(vis[i] == false){ callDfs(vis, adj, i); ans++; } } return ans;

[@zebra-er6xc]

can someone explain if the graph in question is 1 based why don't we run the for loop from 1 to V instead of 0 to V-1

[@lavanyam3224]

I've solved it myself after watching your previous lecture on dfs. Thanks a lot striver for building my confidence.. I always thought graphs are tough and never imagined that I would be able to solve it myself!! Thanks again striver, you're gold

[@ombraforza5780]

For anyone who wishes to use the adjacency matrix, here is my code for it. void solve(int node, vector& adj, vector& visited) { visited[node] = true; for (size_t it{0}; it < adj[node].size(); ++it) { if (!visited[it] && adj[node][it]) { solve(it, adj, visited); } } } int numProvinces(vector adj, int V) { vector visited(V, false); int numProvince{0}; for(int node{0}; node < V; ++node) { if(!visited[node]) { ++numProvince; solve(node, adj, visited); } } return numProvince; }

[@user-xy5ln4zh5w]

thanks for sharing

[@peddikarthik7832]

when you are converting given matrix to adjacency matrix , no need to run the inner j loop from zero , you can start from j=i+1 , because the lower indexes are already taken care by the 2 lines inside the loops.

[@VikashKumar-uz4td]

either u can just pushback j on every i , for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 1) { adjacencyList[i].push_back(j); } } } it will give correct adjacency list but will repeat in undirected graph , to not repeat it , just pushback in List till n/2(even) or n+1/2 ( if odd). List will be something like this [ [0,2] , [1] , [0,2] ] in undirected graph , and if run list pushback till n+1/2 then [ [0,2] , [1] ] (caution : only do n+1/2 trick on undirected graph , for directed loop till n)

[@ishitaamod5109]

How we came to know that it's an adj matrix not list? because in the earlier questions as well it was of the type ArrayList adj ?

[@ShivamTh405]

It is mentioned in the question or if it is not you can see the sample test cases, if the input consists of only 1s and 0s, it indicates that adjacency matrix is being used

[@amantripathi4100]

u nailed it bhai

[@arnabdebnath2425]

Bhaiya your godly explaination of dfs made me do this by my own

[@harshitsahu845]

9:18 we dont need adjLs[j].push_back(i) as the nodes will be added twice since the matrix caluclates all the possibilites already

[@_rmnsingh]

right

[@AkshitSharma0]

Exactly

[@user-el6hv6em7m]

understood... Thanks for this amazing series

[@cinime]

Understood! Awesome explanation as always, thank you very much!!

[@kavyabanka4482]

We cannot go from 1-3 how can it is province.

[@saieswarimaddula7012]

thank you again striver for this wonderful series!! Am able to solve before seeing the solution itself..and all thanks to your excellent explanation:)

[@kaichang8186]

understood, great explanation

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@KratosProton]

Great video, just one suggestion Striver sir, can you please add java code snap in white background as it is very difficult to read in dark background in mobile.

[@takeUforward]

Sure will do that from the next set of videos, thanks for the suggestion

[@jitinroy2246]

most underrated comment, for the same thing gonna message him on linkedin/instagram. for the black background we have to increase video quality from 480p to 720p then black board java code can be seen properly. so it's not good for the mobile data user's who have limited data/day.

[@ayushigupta8633]

I solved this problem without seeing your code, only with the amazing explanation

[@ayushidalal5488]

In case anyone is looking for 1-based indexing code: class Solution { void dfs(int node, vector &vis, vector adj[]) { vis[node] = 1; for(auto i: adj[node]) { if(vis[i] == 0) { dfs(i, vis, adj); } } } public: int findCircleNum(vector& isConnected) { // same as no.of components in disconnected graph int n = isConnected.size(); vector adj[n+1]; // convert adjacency matrix into list for(int i=0; i

[@aarnasinghal5057]

thanks and how do we know that in matrix 0 based indexing is being followed and not 1 based indexing? plzz tell

[@krishnarajput4125]

//alternate solution class Solution { public: void dfs(int i,int v,vector adj,vector&vis){ vis[i]=1; for(int it=0;it

[@shaikfahim1232]

Thanks bhayya

[@RahulKumar-qy7pz]

i did it myself .....ywahhhhhhhhhhh feeling so happy woooeeeeeeeewwwwww

[@himanshukaushik9223]

Visited array show error variable size object may not initialise but it is working on gfg why anyone reply??

[@hah314]

Thanks Raj, nice explanation, It helped me a lot to solve it by myself.

[@jagansubramanian5234]

Understood. Keep up the good work. May god bless you ❤

[@vikasbagri1225]

understood it very well... thanks for this revised series

[@taashukumar1155]

matrix +dfs approach:- void dfs(int node,vector adj,int v,vector &vis){ vis[node]=1; for(int i=0;i

[@TON-108]

Thanks!

[@cse048harshkumawat6]

Bhaiya why you can't say it's same as number of components of a graph 😅

[@jonny._.1313]

Same question

[@RaviKumar-mu4ne]

Because its written there....no. of provinces

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@tasneemayham974]

HE'S THE BESTTT AND HEE KNOWWS ITT!!!!!!!! UNDERSTOOD STRIVERR!!

[@hp2805]

Thanks so much thalaiva !

[@AyushEditz-hs6pf]

If we are using 1 based indexing, then why are we not making the visited array of length V+1 and not not iterating into it by the condition for( int i=1 ; " i

[@harshitgupta5718]

I think instead of converting the adjacency matrix to adjacency list also we can solve it and found it pretty easy to implement. Here is my code for the numProvinces function. I have implemented it using python programming language. def numProvinces(self, adj, V): # code here visited = [False] * V def dfs(node): visited[node] = True for i in range(V): if adj[node][i] == 1 and not visited[i]: dfs(i) count = 0 for i in range(V): if not visited[i]: dfs(i) count += 1 return count

[@ayushkumartiwari2684]

I just have a doubt . Why are we not considering the time complexity to calculate the adjacency list {O(n*n)} ??? Also great content . Waiting for full series to drop.

[@rohit2571]

Good observation.

[@chitranjansingh8432]

watch from 11:58 again.

[@sumerrawat6947]

time comp n^2 hi hai bhai

[@ai-lian7572]

SIR in j=0 to j

[@stith_pragya]

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

[@chitranshjain5075]

Completely UNDERSTOOD.

[@jambajuice07]

solving problem aagain , i am sooo confident in graphhhh now i dont even need to play the video

[@rahulsinghshekhawat2487]

This is gold.

[@universalcosmologist3675]

thank you very much

[@RohitKumar-dz8dh]

Understood 😊

[@swarupyeole4984]

From Today I started my Graph Playlist again.

[@fine2981]

how is going?

[@vedant6460]

understood

[@imnischaygowda]

Understood, thank you for the playlist.

[@kumpatisupriya3947]

As usual great explanation......👏👏👏

[@ankurmanna2322]

understood and done by myself mostly

[@Black_Hat_Chiggy]

"understood"

[@herculean6748]

I could solve by myself, thanks striver!

[@dreamyme543]

Understood:)

[@anuragC819]

also is there any approx timeline for remaining videos? eagerly waiting for the full series to drop!

[@sumerrawat6947]

I didn't quite get the time complexity part According to me Let' say we have 4 connected components For component 1 the time complexity for traversal is O(V1+2E1) , where V1, E1 is the number of Nodes and edges of that component 1 For component 2 the time complexity for traversal is O(V2+2E2) , where V2,E2 is the number of Nodes and edges of that component 2 For component 3 the time complexity for traversal is O(V3+2E3) , where V3,E3 is the number of Nodes and edges of that component 3 For component 4 the time complexity for traversal is O(V4+2E4) , where V4 ,E4 is the number of Nodes edges of that component 4 So total time complexity = Sum of time complexity of each component O(V1+2E1) + O(V2+2E2) + O(V3+2E3) + O(V3+2E4) = O(V1+V2+V3+V4) + O(2E1+2E2+2E3+2E4) = O(N) + O(2E) //where N is total nodes in complete graph and E is the total edges in whole graph the total time complexity becomes -> *O(N+2E)* //which is the time complexity to traverse in the whole graph

[@takeUforward]

but you are missing the inner for loop which runs for every traversal.

[@sumerrawat6947]

@@takeUforward bhaiya we are also converting the adj matrix to adj list , for which we traverse the complete matrix , and then we are doing operations with that adj list So actually the time complexity will be O(N^2) 😅 The time complexity will be in the order of N only if we are given the adjacency list directly in the question

[@nsudhir_here]

@@sumerrawat6947 he assumes that Adjacency list is given instead of Adjacency Matric so he doesn't calculate the time complexity for creating Adjacency list from Adjacency Matrix.

[@amansinghal4663]

I also have the same doubt, if you have understood the time complexity part then can you plz explain it to me ? According to me, the time complexity will be O(N+2E) if we ignore the nested for loops for converting matrix into list.

[@pratham654]

Understood very well.

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@LearnerForever123]

Understood

[@444yoshitha8]

I solved the question immediatedly after he said we need to change the given input into adjacency list in less than 1min😝

[@Sillysmiles76]

Thank you, Understood

[@Shivi32590]

thankyou

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@pixelsbyme]

Understood 🔥, thank you for such videos

[@komalkrishna7836]

Understood! nice explanation

[@jatilyadav4000]

Amazing as Always...

[@p38_amankuldeep75]

Enjoyed very much💙💙💙

[@GhostRider....]

Nice Explanation Bhaiya

[@suyashapokharna873]

understood striver bhaiya

[@abhijitroy1958]

great explanation of tc

[@dilsedhoni9229]

Understood Striver! Thanks ;-)

[@Fuzail_Ahammed]

Very nice explanation ✨

[@suheabkhan2546]

understood very very well

[@shaikazam5559]

Not subscribing and liking is very injustice to strivers talent and hard work we can atleast do this for our gem

[@tasneemayham974]

Every time Striver says to subscribe, I go down to subscribe and find I am already subscribed!!

[@dank7044]

did this on my own

[@rishabhgupta9846]

great explanation

[@morganyu3391]

Understood bhaiya!!

[@user-tk2vg5jt3l]

Thank you bhaiya

[@garvitkhandelwal1860]

bro is TUF working ?

[@aditya_raj7827]

Love you striver ❤

[@vishnu9134]

Understood ❤

[@harshvardhansingh2272]

understood striver

[@_hulk748]

understood sir🙇‍♂🙏❤

[@shubhigupta5689]

Understood🌻

[@girlneedsnoname9488]

what is the difference between finding # of islands and finding # of provinces ? is it just the way graph is represented ?

[@imyasharya]

understood!

[@RitikKumar-bk6pj]

Sir yes wale series jada best hai phle ke comparison mai problems ka intuition kafe clear hua isse

[@lakeshkumar8239]

understood sir

[@arvindg553]

This is gold

[@mriduljain1981]

understood.

[@rajsekhardutta8891]

Understood!🤩

[@VikashKumar-uz4td]

looks confusing , adjacency list is printing wrong, here is my version for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (adj[i][j] == 1) { adjacencyList[i].push_back(j); } } } List will be something like this [ [0,2] , [1] , [0,2] ] in undirected graph , and if u will run list.push_back till n+1/2 then [ [0,2] , [1] ] (caution : only do n+1/2 trick on undirected graph , for directed loop till n)

[@ISHARAMTEKE-ku2ll]

code using BFS traversal : using the list approch i.e creating another adjacency list. int findNumOfProvinces(vector& roads, int n) { vector adjls(n); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(roads[i][j] == 1 && i != j) { adjls[i].push_back(j); adjls[j].push_back(i); } } } vector vis(n, 0); // Initialize all values to 0 int cnt = 0; for(int i = 0; i < n; i++) { if(!vis[i]) { queue q; vis[i] = 1; q.push(i); cnt++; while(!q.empty()) { int node = q.front(); q.pop(); for(auto it : adjls[node]) { if(!vis[it]) { vis[it] = 1; q.push(it); } } } } } return cnt; } // Without creating Adjacency list ,using given matrix only int findNumOfProvinces(vector& roads, int n) { vector vis(n, 0); // Initialize all values to 0 int cnt = 0; for(int i = 0; i < n; i++) { if(!vis[i]) { queue q; vis[i] = 1; q.push(i); cnt++; while(!q.empty()) { int node = q.front(); q.pop(); for(int j = 0; j < n; j++) { if(roads[node][j] == 1 && !vis[j]) { vis[j] = 1; q.push(j); } } } } } return cnt; }

[@ooofrg4492]

I have problem in time complexity I think it should be o(v^2)+o(v+2e). Am I false then please give reason.

[@chirag2819]

Boolean[] vis is better choice then int[] vis

[@ayat_middya]

Wonderful.....❤️

[@suhaanbhandary4009]

understood!!

[@ashitasrivastava681]

UNDERSTOOD