省份数量00

题目链接

省份数量

题目描述

注意点

• 1 <= n <= 200
• isConnected[i][j] 为 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

解答思路

• 最初想到的是广度优先遍历，当某个城市不属于省份，需要从该城市开始，根据isConnected找到所有与其相连的城市，即可得到省份中有哪些城市，保存城市所属省份的信息，遍历完全部城市以后，即可得到连通分量的总数，即省份的总数
• 另一个方法就是深度优先遍历找到相连的城市，找到一个属于新的省份的城市后，找到与之相连的城市，再根据相连的城市找到与相连城市相连的城市…找到省份中所有的城市。遍历完全部城市，找到所有省份

代码

方法一：

class Solution {public int findCircleNum(int[][] isConnected) {int res = 0;int n = isConnected.length;int[] province = new int[n];Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < n; i++) {// 该城市已经属于某个省份if (province[i] != 0) {continue;}res++;deque.offerLast(i);// 找到与i相连的所有城市while (!deque.isEmpty()) {int row = deque.pollFirst();for (int j = 0; j < n; j++) {if (isConnected[row][j] == 1 && province[j] == 0) {province[j] = res;deque.offerLast(j);}}}}return res;}
}

方法二：

class Solution {public int findCircleNum(int[][] isConnected) {int res = 0;int n = isConnected.length;int[] province = new int[n];for (int i = 0; i < n; i++) {// 该城市已属于某个省份if (province[i] != 0) {continue;}res++;// 深度优先遍历找到属于该省份的城市dfs(isConnected, province, i);}return res;}public void dfs(int[][] isConnected, int[] province, int i) {if (province[i] != 0) {return;}province[i] = 1;for (int j = 0; j < province.length; j++) {if (isConnected[i][j] == 1) {dfs(isConnected, province, j);}}}
}

关键点

• 深度优先遍历的思想
• 广度优先遍历的思想
• 需要保存城市属于某个省份的信息