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

[@AtulKumar-c4x7l]

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?

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

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

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

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

[@NavyasriThalluri]

thanks for sharing

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

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

[@arnabdebnath2425]

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

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

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

[@cinime]

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

[@kavyabanka4482]

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

[@lavanya_m01]

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

[@ayushigupta8633]

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

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

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

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

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

[@ramanpareek5218]

liked the video, notes taken, understood

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

[@ai-lian7572]

SIR in j=0 to j

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

[@jambajuice07]

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

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

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

[@himanshukaushik9223]

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

[@prathimabhat9670]

Not sure if you have corrected but time complexity of this solution should be O(N^2) if I am not wrong?

[@VarshaSingh-hi2sb]

same doubt

[@thatboysus-tm]

Let me clear this out : You are correct, It would be O(n^2) when you are solving it for adjacency matrix But here, Striver is taking into assumption that we have applied bfs in which there was adjacency list so with that in mind time complexity would be O(N) + O(V+2E) Hope it clears your doubt ✌️

[@VikasBagri-i5j]

understood... Thanks for this amazing series

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@amantripathi4100]

u nailed it bhai

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

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

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

[@swarupyeole4984]

From Today I started my Graph Playlist again.

[@fine2981]

how is going?

[@RitikKumar-bk6pj]

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

[@kaichang8186]

understood, great explanation

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

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

[@tasneemayham974]

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

[@anuragC819]

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

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

[@it.b.61.prashantsingh87]

I think bhaiya, if u don't add adjLis[j].push_back(i), it will work fine, correct me plzz, if i wrong

[@swapnav532]

for(int i=1;i

[@chitranshjain5075]

Completely UNDERSTOOD.

[@RahulKumar-qy7pz]

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

[@stith_pragya]

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

[@vakhariyajay2224]

Thank you very much. You are a genius.

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

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

[@suyashapokharna873]

understood striver bhaiya

[@GhostRider....]

Nice Explanation Bhaiya

[@anshuroy5961]

are v and n same ? both are reffering to total no of nodes?

[@ankurmanna2322]

understood and done by myself mostly

[@imnischaygowda]

Understood, thank you for the playlist.

[@saiharshapingali7577]

cant we do it as implicit matrix dfs ? like number of islands ?

[@herculean6748]

I could solve by myself, thanks striver!

[@kumpatisupriya3947]

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

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@mokshmangal9308]

@striver bhiya can we do this question without making adjacency list.

[@girlneedsnoname9488]

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

[@ajaysarkate6624]

In function parameter, its already given adj list, then how we are converting from matrix to list? Not getting this

[@hp2805]

Thanks so much thalaiva !

[@Manish-ww3lg]

in question 1 based graph is given but you wrote code for 0 based graph.why???

[@rahulsinghshekhawat2487]

This is gold.

[@dilsedhoni9229]

Understood Striver! Thanks ;-)

[@sowrimihiryss]

In Time complexity it was said as O(N)+O(V+2E). But here N and V are same isn't it?

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

[@DakshTripathi-w7o]

can somebody explain why the TC was O(V) + O(V+2E) instead of O(V)*O(V+2E) , I did not get this part

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@Sillysmiles76]

Thank you, Understood

[@444yoshitha8]

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

[@morganyu3391]

Understood bhaiya!!

[@rakshitdevra7060]

There is a slight error in java code while converting Adjacency matrix to list in if condition if(adj[i][j]==1 && i!=j)

[@dank7044]

did this on my own

[@pratham654]

Understood very well.

[@abhijitroy1958]

great explanation of tc

[@p38_amankuldeep75]

Enjoyed very much💙💙💙

[@RohitKumar-dz8dh]

Understood 😊

[@komalkrishna7836]

Understood! nice explanation

[@pixelsbyme]

Understood 🔥, thank you for such videos

[@Fuzail_Ahammed]

Very nice explanation ✨

[@samarthsairam3512]

how do we apply the same approach for finding the number of connected components in an undirected graph?

[@princeaharwal3391]

In this question, he is talking about undirected graphs.

[@kausachan4167]

regarding time complexity O(v + 2e) so that v is for the first for-loop right?

[@suheabkhan2546]

understood very very well

[@jatilyadav4000]

Amazing as Always...

[@sudarshanjha8594]

i have a doubt first you declare a array having all element as zero then you are checking if its element is zero mujhe samajh nahi aaya

[@universalcosmologist3675]

thank you very much

[@rishabhgupta9846]

great explanation

[@shreyamaheshwari7329]

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

[@pulkitbatra1083]

for me it is also showing seg fault😥

[@vanshajsingla03722]

// Actually while converting adj. matrix to adj. list he converted graph to 0-based indexing instead of 1-based indexing. // So, we can do in both ways. // This is the code with 1-based indexing void dfs(int s,vectoradjLs[],int vis[]) { vis[s]=1; for(auto it:adjLs[s]) { if(!vis[it]) { dfs(it,adjLs,vis); } } } int numProvinces(vector adj, int V) { // code here // adj matrix to list vectoradjLs[V+1]; for(int i=0;i

[@sachinbhagat8199]

@@vanshajsingla03722 got it👍

[@dreamyme543]

Understood:)

[@harshvardhansingh2272]

understood striver

[@anuragC819]

why are we doing from gfg? the java versions of many problems are very poorly constructed. the function often has bad variable names, you dont exactly know what each variable signifies. leetcode remains much better, in my opinion

[@dipendersingh1536]

I guess this series is sponsored by GFG so that’s why maybe……

[@takeUforward]

You can google the problem name, and solve it. As long as you understand the explanation, it should be fine ✌🏼

[@parthdurgude2617]

understood!!!

[@user-cn2lx2qf4z]

how TC is O(n)+O(V+2E) instead of O(n)*O(V+2E)

[@Learnprogramming-q7f]

Thank you bhaiya

[@garvitkhandelwal1860]

bro is TUF working ?