Number of Provinces LeetCode solution in C++

1
class Solution {
2
 private:
3
  void dfs(int node, vector<vector<int>> &graph, int n, vector<bool> &vis) {
4
    vis[node] = true;
5

6
    for (int j = 0; j < graph[node].size(); j++) {
7
      if (graph[node][j] == 1 and !vis[j]) {
8
        dfs(j, graph, n, vis);
9
      }
10
    }
11
  }
12

13
 public:
14
  int findCircleNum(vector<vector<int>> &isConnected) {
15
    int n = isConnected.size();
16

17
    vector<bool> vis(n, false);
18

19
    int ans = 0;
20

21
    for (int i = 0; i < n; i++) {
22
      if (!vis[i]) {
23
        ans++;
24
        dfs(i, isConnected, n, vis);
25
      }
26
    }
27

28
    return ans;
29
  }
30
};