aboutsummaryrefslogtreecommitdiff
path: root/number_provinces.cpp
blob: e26785408d8ead0fba0f254f3d191a2ebb0b0926 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 547. Number of Provinces
#include "leetcode.h"

/*
 * dthere 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. given an 'n x n' matrix 'is_connected' where
 * 'is_connected[i][j] = 1' if the i'th city and the j'th city are directly
 * connected, and 'is_connected[i][j] = 0' otherwise. return the total number of
 * provinces
 */

class Solution {
  void dfs(int i, vvd(int) & is_connected, vector<bool> &vis) {
    vis[i] = true;
    for (int j = 0; j < vis.size(); j++)
      if (i != j && is_connected[i][j] && !vis[j])
        dfs(j, is_connected, vis);
  }

public:
  int findCircleNum(vvd(int) & is_connected) {
    if (is_connected.empty())
      return 0;
    int n = is_connected.size(), groups = 0;
    vector<bool> vis(n, false);
    for (int i = 0; i < vis.size(); i++)
      groups += !vis[i] ? dfs(i, is_connected, vis), 1 : 0;
    return groups;
  }
};

int main() {
  Solution obj;
  vvd(int) ic1 = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
  vvd(int) ic2 = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  printf("%d\n", obj.findCircleNum(ic1)); // expect: 2
  printf("%d\n", obj.findCircleNum(ic2)); // expect: 3
}