【LeeCode】547. 省份数量--unknow

【题目描述】

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

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

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

返回矩阵中 省份 的数量。

https://leetcode.cn/problems/number-of-provinces/

【示例】

【代码】

思路： 没想明白

package com.company;
import java.util.*;

// 2023-04-24
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int len = isConnected.length;
        boolean[] visited = new boolean[len];
        int sum = 0;

        for (int i = 0; i < len; i++){
            if (!visited[i]){
                dfs(isConnected, visited, len, i);
                sum++;
            }
        }
        System.out.println(sum);
        return sum;
    }

    private  void dfs(int[][] isConnected, boolean[] visited, int len, int i) {
        // 对当前顶点 i 进行访问标记
        visited[i] = true;
        
        // 继续遍历与顶点 i 相邻的顶点（使用 visited 数组防止重复访问）
        for (int j = 0; j < len; j++){
            if (isConnected[i][j] == 1 && !visited[j]){
                dfs(isConnected, visited, len, j);
            }
        }
    }
}
public class Test {
    public static void main(String[] args) {
        new Solution().findCircleNum(new int[][]{{1,1,0}, {1,1,0}, {0,0,1}}); // 输出：2
        new Solution().findCircleNum(new int[][] {{1,0,0},{0,1, 0},{0,0,1}}); // 输出：3
    }
}