aboutsummaryrefslogtreecommitdiff
path: root/max_network_rank.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 /max_network_rank.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'max_network_rank.c')
-rw-r--r--max_network_rank.c42
1 files changed, 42 insertions, 0 deletions
diff --git a/max_network_rank.c b/max_network_rank.c
new file mode 100644
index 0000000..44c1ed3
--- /dev/null
+++ b/max_network_rank.c
@@ -0,0 +1,42 @@
+// 1615. Maximal Network Rank
+#include <limits.h>
+#include <math.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+/*
+ * there is an infrastructure of 'n' cities with some number of 'roads'
+ * connecting these cities. each 'roads[i] = [ai, bi]'. indicates that there is
+ * a bidirectional road between cities 'ai' and 'bi'. the network rank of two
+ * different cities is defined as the total number of directly conncected roads
+ * to either city. if a road is directly connected to both cities, it is only
+ * counted once. the maximal network rank of the infrastructure is the maximum
+ * network rank of all pairs of different cities. given the integer 'n' and the
+ * array 'roads', return the maximal network rank of the entire infrastructure.
+ */
+
+int maximalNetworkRank(int n, int **roads, int roads_size,
+ int *roads_col_size) {
+ bool **connect = malloc(n * sizeof(bool *));
+ for (int i = 0; i < n; i++)
+ connect[i] = calloc(n, sizeof(bool));
+ int *edges = calloc(n, sizeof(int));
+ for (int i = 0; i < roads_size; i++) {
+ int a = roads[i][0];
+ int b = roads[i][1];
+ connect[a][b] = true;
+ connect[b][a] = true;
+ edges[a]++;
+ edges[b]++;
+ }
+ int ans = INT_MIN;
+ for (int i = 0; i < n; i++)
+ for (int j = i + 1; j < n; j++) {
+ int rank = edges[i] + edges[j] - connect[i][j];
+ ans = fmax(ans, rank);
+ }
+ for (int i = 0; i < n; i++)
+ free(connect);
+ free(connect), free(edges);
+ return ans;
+}