547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

class Solution {
    void chk(vector<bool>& v, vector<vector<int>>& c, int& n, int p) {
        v[p] = true;
        for(int i = 0; i < n; i++) {
            if(c[i][p] && !v[i])
                chk(v,c,n,i);
        }
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size(), res = 0;
        vector<bool> v(n, false);
        for(int i = 0; i < n; i++) {
            if(v[i]) continue;
            res++;
            chk(v, isConnected, n, i);
        }
        return res;
    }
};