给定一个 n 个节点的邻接矩阵 m。 节点定义为城市,如果 a 城市与 b 城市相连, b 与 c 城市相连,尽管 a 与 c 并不直接相连,但可以认为 a 与 c 相连,定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,否则表示不相连。
请你找出共有多少个城市群。
数据范围: , 矩阵中只包含和
[[1,1,0],[1,1,0],[0,0,1]]
2
1 2 相连,3 独立,因此是 3 个城市群。
[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]
2
1 , 2相连 ;2 ,3相连,4独立,因此是 1,2,3 属于一个城市群,4属于一个城市群。
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); } } } }