有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。

省份 是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

返回矩陣中 省份 的數量。

示例 1：

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

代碼

class Solution {public int findCircleNum(int[][] isConnected) {Map<Integer,List<Integer>> map=new HashMap<>();boolean[] check=new boolean[isConnected.length];for(int i=0;i<isConnected.length;i++)//記錄鄰接點{map.put(i,new ArrayList<>());}for(int i=0;i<isConnected.length;i++){for(int j=i+1;j<isConnected[i].length;j++){if(isConnected[i][j]==1){map.get(i).add(j);map.get(j).add(i);}}}int res=0;for(int i=0;i<isConnected.length;i++)//bfs{if(!check[i]){Queue<Integer> queue=new LinkedList<>();queue.add(i);check[i]=true;while (!queue.isEmpty()){int cur=queue.poll();for(int c:map.get(cur)){if(check[c]) continue;check[c]=true;queue.add(c);}}res++;}}return res;} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的leetcode 547. 省份数量（bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。