Find the Number of Provinces

Problem Link:

1. https://www.codingninjas.com/studio/problems/find-the-number-of-states_1377943?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf

2. https://leetcode.com/problems/number-of-provinces/description/

Hint Video:

Code:

void bfs(vector<int> adjLs[], 
    vector<int>& visited, int start){

    visited[start] = 1;

    queue<int> q;
    q.push(start);

    while(!q.empty()){
        int node = q.front();
        q.pop();

        for(auto &it: adjLs[node]){
            if(!visited[it]){
                visited[it] = 1;
                q.push(it);
            }
        }
    }

    return;

}

int findNumOfProvinces(vector<vector<int>>& roads, int n) {
    // Write your code here.

    vector<int> 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<int> vis(n,0);

    int count = 0;

    for(int i=0;i<n;i++){
        if(!vis[i]){
            bfs(adjLs,vis,i);
            count++;
        }
    }

    return count;
}