547. Number of Provinces

 一刷 06/2022

Version #1 DFS

Time - O(N^2) since the graph is traversed once

Space O(N) for the visited array

Runtime: 1 ms, faster than 99.93% of Java online submissions for Number of Provinces.

Memory Usage: 53.4 MB, less than 76.07% of Java online submissions for Number of Provinces.

class Solution {

    public int findCircleNum(int[][] isConnected) {

        if (isConnected == null || isConnected.length == 0 || isConnected[0] == null || isConnected[0].length == 0) {

            return 0;

        }

        int N = isConnected.length;

        boolean[] visited = new boolean[N];

        int count = 0;

        for (int i = 0; i < N; i++) {

            if (visited[i]) {

                continue;

            }

            count++;

            visited[i] = true;

            // DFS

            dfs(isConnected, i, visited);

        }

        return count;

    }

    

    private void dfs(int[][] isConnected, int i, boolean[] visited) {

        for (int j = 0; j < isConnected.length; j++) {

            if (visited[j] || isConnected[i][j] == 0) {

                continue;

            }

            visited[j] = true;

            dfs(isConnected, j, visited);

        }

    }

}