LeetCode547—省份数量（java版）_有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且

题目描述：

标签：深度优先搜索  广度优先搜索  并查集  图

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

代码：

 思路分析：无向图类型

1、定义一个boolean数组hasVisited记录该节点是否被访问过

2、遍历n个节点，如果没有访问过，就对该节点进行dfs搜索

3、定义dfs方法，先将该节点修改为访问过true，然后对（i,k），k从0~n-1遍历，如果isConnected[i][k]=1且k没有被访问过，则继续沿着k进行dfs搜索。

class Solution {
    private int n;
 
    public int findCircleNum(int[][] isConnected) {
        n = isConnected.length;
        int circleNum = 0;
        boolean[] hasVisited = new boolean[n];
        for(int i = 0;i < n;i++){
            if(!hasVisited[i]){
                dfs(isConnected, i, hasVisited);
                circleNum++;
            }
        }
        return circleNum;
    }
 
    public void dfs(int[][] isConnected, int i, boolean[] hasVisited){
        hasVisited[i] = true;
        for(int k = 0;k < n;k++){
            if(isConnected[i][k] == 1 && !hasVisited[k]){
                dfs(isConnected, k , hasVisited);
            }
        }
    }
}