题目解析

城市群数量_牛客题霸_牛客网

当解决这个问题时，首先需要理解题目要求。题目中给出了一个城市之间的邻接矩阵，矩阵中的元素表示城市之间是否直接相连。如果两个城市直接相连，或者通过其他城市间接相连，它们就属于同一个城市群。

思路分析

为了解决这个问题，图的遍历可以使用深度优先搜索（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);
            }
        }
    }
}