From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- max_network_rank.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 max_network_rank.cpp (limited to 'max_network_rank.cpp') 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> 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 +} -- cgit v1.2.3