题解 | #城市群数量# [P0-T1]

最普通的DFS

DFS了几遍就有几个城市群。

import java.util.*;

public class Solution {
  boolean[] visited;
  int ans = 0;
  
  public int citys (ArrayList<ArrayList<Integer>> m) {
    visited = new boolean[m.size()];
    for (int i = 0; i < m.size(); i++) {
      if (visited[i]) continue;
      ans++;
      dfs(i, m);
    }
    return ans;
  }
  
  void dfs(int i, ArrayList<ArrayList<Integer>> m) {
    if (visited[i]) return;
    
    visited[i] = true;
    ArrayList<Integer> neis = m.get(i);
    for(int j = 0; j < neis.size(); j++) {
      if (neis.get(j) == 1) dfs(j, m);
    }
  }
}