力扣-省份数量

思路分析

1. BFS 解决该问题的核心是找连通分量的数量：
2. 初始化：用访问数组标记每个城市是否被遍历过，初始全为未访问；省份计数器初始为 0。
   • 遍历所有城市：对于每个未被访问的城市，启动一次 BFS：
   • 省份计数器 + 1（代表发现一个新省份）；
   • 将该城市加入队列，标记为已访问；
3. 层序遍历队列中的城市，找到所有与之直接 / 间接相连的城市，标记为已访问（归入当前省份）。
   终止条件：所有城市遍历完毕，计数器即为省份数量。

代码实现

publicintfindCircleNum(int[][]isConnected){// 城市数量intn=isConnected.length;// 访问标记数组，用于记录每个城市是否被访问过boolean[]visited=newboolean[n];// 定义队列用于bfs遍历Deque<Integer>queue=newLinkedList<>();// 定义相连的城市数量intprovinceCount=0;// 遍历所有城市for(inti=0;i<n;i++){// 若该城市未被访问过if(!visited[i]){// 标记被访问过visited[i]=true;// 该城市入队列queue.offer(i);// bfs遍历所有与该城市相连的城市while(!queue.isEmpty()){// 队首元素出队列Integerpop=queue.pop();for(intj=0;j<n;j++){// 若该城市未被访问过且与当前城市相连if(!visited[j]&&isConnected[pop][j]==1){// 标记被访问过visited[j]=true;// 该城市入队列queue.offer(j);}}}// 遍历完所有与该城市相连的城市后，相连的城市数量加1provinceCount++;}}returnprovinceCount;}

复杂度分析

• 总体时间复杂度：O(n²)
  • 外层循环n次
  • 每次BFS内部的内层循环总共执行n次（检查所有城市）
  • 虽然有嵌套结构，但每个节点只被访问一次，总时间复杂度为O(n²)
• 空间复杂度：O(n)
  • visited数组：O(n) - 存储每个城市是否被访问
  • queue队列：最坏情况下O(n) - 在极端情况下，所有城市可能同时在队列中
  • 其他变量：O(1)

注意：provinceCount要在这个省份的所有城市都遍历结束后再去+1，而不要写到visited[j]后面。
一定要理解好题目，题目是要求省份的数量，当多个城市相连时，这些城市只能算是一个省，如果直接在遍历时，即在visited[j]后面就将provinceCount+1的话，就会导致每个城市相连就像省份数量+1，从而导致省份数量严重被高估。
举例说明：
假设有3个城市，连接关系如下：

isConnected = [ [1,1,0], [1,1,0], [0,0,1] ]

• 城市0和城市1相连（同一省份）
• 城市2独立（另一个省份）
• 正确答案应该是2个省份

如果把provinceCount++放在visited[j] = true之后：

• 当i=0时，会访问城市0和1，provinceCount会增加多次
• 当i=2时，会访问城市2，provinceCount再增加
• 结果就不正确了