題目解析

城市群數量_牛客題霸_牛客網

當解決這個問題時，首先需要理解題目要求。題目中給出了一個城市之間的鄰接矩陣，矩陣中的元素表示城市之間是否直接相連。如果兩個城市直接相連，或者通過其他城市間接相連，它們就屬于同一個城市群。

思路分析

為了解決這個問題，圖的遍歷可以使用深度優先搜索（DFS）或者廣度優先搜索（BFS）來遍歷城市，并標記城市所屬的城市群。具體步驟如下：

1. 創建一個布爾類型的數組?visited，用于標記每個城市是否被訪問過。
2. 遍歷所有城市，對于每個未被訪問過的城市，進行深度優先搜索或者廣度優先搜索，并標記所有與該城市直接或間接相連的城市為同一個城市群。
3. 統計不同的城市群數量。

?

代碼實現?
?

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param m int整型ArrayList<ArrayList<>>* @return int整型*/int n,count;boolean[] flags;ArrayList<ArrayList<Integer>> lists;public int citys (ArrayList<ArrayList<Integer>> lists) {this.lists = lists;if (lists == null || lists.isEmpty()) {return 0;}n = lists.size();flags = new boolean[n];for (int i = 0; i < n; i++) {if (!flags[i]) { //把所有沒被標記的都遍歷一遍count++;dfs(i);}}return count;}private void dfs(int pos) {flags[pos] = true;//已經搜索過了for (int i = 0; i < n; i++) {//搜索出所有與pos相鄰的房子if (!flags[i] && lists.get(i).get(pos) == 1) {dfs(i);}}}
}