有 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 示例 2：
输入：isConnected = [1，0，0]，[0，1，0] 输出：3
提示：
1 <= n <= 200 n == isConnected.length n == isConnected[i].length isConnected[i][j] 为 1 或 0 isConnected[i][i] == 1 isConnected[i][j] == isConnected[j][i]
方法1：深度优先搜索
class Solution { public int findCircleNum(int[][] isConnected) { int provinces = isConnected.length; boolean[] visited = new boolean[provinces]; int circles = 0; for (int i = 0; i < provinces; i ) { if (!visited[i]) { dfs(isConnected, visited, provinces, i); circles ; } } return circles; }
public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) { for (int j = 0; j < provinces; j ) { if (isConnected[i][j] == 1 && !visited[j]) { visited[j] = true; dfs(isConnected, visited, provinces, j); } } } }
方法二：广度优先搜索
class Solution { public int findCircleNum(int[][] isConnected) { int provinces = isConnected.length; boolean[] visited = new boolean[provinces]; int circles = 0; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < provinces; i ) { if (!visited[i]) { queue.offer(i); while (!queue.isEmpty()) { int j = queue.poll(); visited[j] = true; for (int k = 0; k < provinces; k ) { if (isConnected[j][k] == 1 && !visited[k]) { queue.offer(k); } } } circles ; } } return circles; } }