牛客对应题目链接：城市群数量_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
1、并查集
2、dfs（经典 floodfill 算法）
使用深度优先搜索（DFS）算法来遍历所有城市，然后统计城市群的数量。
3、bfs（经典 floodfill 算法）
使用广度优先搜索（BFS）算法来遍历所有城市，然后统计城市群的数量。从一个起始城市开始，将其加入队列，然后依次访问队列中的城市，并将其相连的未访问过的城市加入队列，直到队列为空。
二、代码
1、并查集
class Solution { public: int find(int x, vector<int>& p) { if(p[x]!=x) p[x]=find(p[x], p); return p[x]; } int citys(vector<vector<int> >& m) { int n=m.size(); vector<int> p(n); for(int i=0; i<n; i++) p[i]=i; for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(i!=j && m[i][j]==1) p[find(i, p)]=find(j, p); int res=0; for(int i=0; i<n; i++) if(i==p[i]) res++; return res; } };
2、dfs
class Solution { private: bool vis[201]={false}; public: void dfs(vector<vector<int> >& m, int i) { vis[i]=true; for(int j=0; j<m[i].size(); j++) { if(!vis[j] && m[i][j]==1) dfs(m, j); } } int citys(vector<vector<int> >& m) { int n=m.size(); int res=0; for(int i=0; i<n; i++) { if(!vis[i]) { res++; dfs(m, i); } } return res; } };
3、bfs
class Solution { private: int n; queue<int> q; bool vis[201]={false}; public: void bfs(vector<vector<int>>& m, int st) { q.push(st); vis[st]=true; while(q.size()) { int t=q.front(); q.pop(); for(int i=0; i<n; i++) { if(!vis[i] && t!=i && m[t][i]==1) { q.push(i); vis[i]=true; } } } } int citys(vector<vector<int> >& m) { n=m.size(); int res=0; for(int i=0; i<n; i++) { if(!vis[i]) { res++; bfs(m, i); } } return res; } };
三、反思与改进
记录一下这道题的多种做法。
