547. Number of Provinces

PHOTO EMBED

Sun Mar 19 2023 09:43:36 GMT+0000 (Coordinated Universal Time)

Saved by @Ranjan_kumar #c++

class Solution {
public:
    int c=0;
    
    void bfs(vector<vector<int>>& isConnected, vector<bool> &v, int i,  unordered_map<int, set<int>> &m)
    {
        queue<int> q;
        q.push(i);
        v[i]=true;
        while(!q.empty())
        {
            int p=q.front();
            q.pop();
            
            for(auto x:m[p])
            {
                if(!v[x])
                {
                    q.push(x);
                    v[x]=true;
                }
            }
        }
    }
    void makeadj(vector<vector<int>> &isConnected, unordered_map<int, set<int>> &m)
    {
        int n=isConnected.size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(isConnected[i][j]==1)
                {
                    m[i+1].insert(j+1);
                    m[j+1].insert(i+1);
                }
            }
        }
    }
    
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        vector<bool> v(n+1,false);
        unordered_map<int, set<int>> m;
        makeadj(isConnected, m);
        for(int i=1;i<=n;i++)
        {
            if(!v[i])
            {
                c++;
                bfs(isConnected, v, i, m);
            }
        }
        return c;
    }
};
content_copyCOPY

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