aboutsummaryrefslogtreecommitdiff
path: root/number_provinces.c
blob: f2cf4991a9d50393fb46d598a9ca5fba7d0413b1 (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
42
43
44
45
46
47
48
// 547. Number of Provinces
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.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
 */

void dfs(int **is_connected, bool *vis, int n, int i) {
  for (int j = 0; j < n; j++) {
    if (is_connected[i][j] && !vis[j]) {
      is_connected[i][j] = 0;
      vis[j] = true;
      dfs(is_connected, vis, n, j);
    }
  }
}

int findCircleNum(int **is_connected, int is_connected_size,
                  int *is_connected_col_size) {
  int ans = 0;
  bool *vis = calloc(is_connected_size, sizeof(bool));
  for (int i = 0; i < is_connected_size; i++) {
    if (is_connected[i][i] && !vis[i]) {
      ans++;
      vis[i] = true;
      is_connected[i][i] = 0;
      dfs(is_connected, vis, is_connected_size, i);
    }
  }
  free(vis);
  return ans;
}

int main() {
  int ic1[3][3] = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}, ics1 = 3, *iccs1;
  int ic2[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}, ics2 = 3, *iccs2;
  printf("%d\n", findCircleNum(ic1, ics1, iccs1)); // expect: 2
  printf("%d\n", findCircleNum(ic2, ics2, iccs2)); // expect: 3
}