-
Notifications
You must be signed in to change notification settings - Fork 0
/
Number of Provinces.cpp
37 lines (36 loc) · 1.04 KB
/
Number of Provinces.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
Problem Link: https://practice.geeksforgeeks.org/problems/number-of-provinces/1
*/
class Solution{
private:
void dfs(int node, vector<int> adjLS, int vis[]){
vis[node]=1;
for(auto &it: adjLS[node]){
if(!vis[it]){
dfs(it, adjLS, vis);
}
}
}
public:
int numOfProvinces(vector<vector<int>> adj, int V){
vector<int> adjLS(V);
// conversion of adjacency matrix to list
for(int i=0; i<V; i++){
for(int j=0; j<V; j++){
if(adj[i][j] == 1 && i!=j){
adjLS[i].push_back(j);
adjLS[j].push_back(i);
}
}
}
int vis[V]={0};
int cnt=0;
for(int i=0; i<V; i++){
if(!vis[i]){
cnt++; // this will give the answer
dfs(i, adjLS, vis);
}
}
return cnt;
}
}