城市群数量

[编程题]城市群数量

热度指数：1531 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n 个节点的邻接矩阵 m。节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，但可以认为 a 与 c 相连，定义 a,b,c 是一个城市群。

矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。

请你找出共有多少个城市群。

数据范围： $1 \le n \le 200 \$ ，矩阵中只包含 $0 \$ 和 $1 \$

示例1

输入

[[1,1,0],[1,1,0],[0,0,1]]

输出

说明

1 2 相连，3 独立，因此是 3 个城市群。

示例2

输入

[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]

输出

说明

1 ， 2相连 ；2 ，3相连，4独立，因此是 1,2,3 属于一个城市群，4属于一个城市群。

算法知识视频讲解

Java

Melody96

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
    public int citys (ArrayList<ArrayList<Integer>> m) {
        // write code here
        int n = m.size();
        int k = m.get(0).size();
//         int[][] arr = new int[n][k];
        
        int[] visited = new int[n];
        int ans = 0;
        for(int i = 0;i<n;i++){
//             System.out.println(i);
            if(visited[i] == 0){
                ans++;
                dfs(m,visited,i);
            }
        }
        return ans;
    }
    
    public void dfs(ArrayList<ArrayList<Integer>> m,int[] visited,int node){
        visited[node] = 1;
        ArrayList<Integer> arr = m.get(node);
        for(int i = 0;i<arr.size();i++){
            if(arr.get(i)!=0 && visited[i] == 0){
                dfs(m,visited,i);
            }
        }
    }
}

发表于 2022-03-21 12:00:38 回复(0)