// DFS solution: visited array
// Time: O(n^2), 1ms
// Space: O(n), 44.6mb
class Solution {
    public int findCircleNum(int[][] M) {
        int ans = 0;
        int visited[] = new int[M.length];
        for(int i = 0; i < M.length; i++) {
            if(M[i][i] == 1 && visited[i] == 0) {
                ans++;
                deleteCircle(M, i, visited);
            }
        }
        return ans;
    }

    // Helper method
    private void deleteCircle(int[][] M, int i, int[] visited) {
        // Base case: already delete that user
        if(visited[i] == 1) return;
        visited[i] = 1;
        // For all the friends that the user has
        for(int j = 0; j < M[0].length; j++) {
            if(M[i][j] == 1) deleteCircle(M, j, visited);
        }
    }
}