aboutsummaryrefslogtreecommitdiff
path: root/number_provinces.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /number_provinces.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'number_provinces.c')
-rw-r--r--number_provinces.c48
1 files changed, 48 insertions, 0 deletions
diff --git a/number_provinces.c b/number_provinces.c
new file mode 100644
index 0000000..f2cf499
--- /dev/null
+++ b/number_provinces.c
@@ -0,0 +1,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
+}