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; } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter