aboutsummaryrefslogtreecommitdiff
path: root/max_network_rank.cpp
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.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'max_network_rank.cpp')
-rw-r--r--max_network_rank.cpp44
1 files changed, 44 insertions, 0 deletions
diff --git a/max_network_rank.cpp b/max_network_rank.cpp
new file mode 100644
index 0000000..14a5f8f
--- /dev/null
+++ b/max_network_rank.cpp
@@ -0,0 +1,44 @@
+// 1615. Maximal Network Rank
+#include "leetcode.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.
+ */
+
+class Solution {
+public:
+ int maximalNetworkRank(int n, vvd(int) & roads) {
+ vector<unordered_set<int>> graph(n);
+ for (auto r : roads) {
+ graph[r[0]].insert(r[1]);
+ graph[r[1]].insert(r[0]);
+ }
+ int maximal = 0;
+ for (int i = 0; i < n; i++) {
+ for (int j = i + 1; j < n; j++) {
+ int network_rank = graph[i].size();
+ if (graph[j].count(i))
+ --network_rank;
+ maximal = max(maximal, network_rank);
+ }
+ }
+ return maximal;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd(int) r1 = {{0, 1}, {0, 3}, {1, 2}, {1, 3}},
+ r2 = {{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 3}, {2, 4}},
+ r3 = {{0, 1}, {1, 2}, {2, 3}, {2, 4}, {5, 6}, {5, 7}};
+ printf("%d\n", obj.maximalNetworkRank(4, r1)); // expect: 4
+ printf("%d\n", obj.maximalNetworkRank(5, r2)); // expect: 5
+ printf("%d\n", obj.maximalNetworkRank(8, r3)); // expect: 5
+}