class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        if (M.empty()) {
            return 0;
        }
        vector<bool> marked(M.size(), false);
        int graphNum = 0;
        for (int i = 0; i < M.size(); ++i) {
            if (!marked[i]) {
                graphNum++;
                dfs(M, marked, i);
            }
        }
        return graphNum;
    }
    
    void dfs(const vector<vector<int>>& M, vector<bool>& marked, int i) {
        marked[i] = true;
        for (int j = 0; j < M.size(); ++j) {
            if (M[i][j] && !marked[j]) {
                dfs(M, marked, j);
            }
        }
    }
};