# 1615. Maximal Network Rank   • Time: $O(n + |\texttt{roads}|)$
• Space: $O(n)$
  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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 class Solution { public: int maximalNetworkRank(int n, vector>& roads) { vector degrees(n); for (const vector& road : roads) { const int u = road; const int v = road; ++degrees[u]; ++degrees[v]; } // Find the first maximum and the second maximum degrees. int maxDegree1 = 0; int maxDegree2 = 0; for (const int degree : degrees) { if (degree > maxDegree1) { maxDegree2 = maxDegree1; maxDegree1 = degree; } else if (degree > maxDegree2) { maxDegree2 = degree; } } // There can be multiple nodes with the maxDegree1 or the maxDegree2. // Find the counts of such nodes. int countMaxDegree1 = 0; int countMaxDegree2 = 0; for (const int degree : degrees) if (degree == maxDegree1) ++countMaxDegree1; else if (degree == maxDegree2) ++countMaxDegree2; if (countMaxDegree1 == 1) { // Case 1: If there is only one node with degree = maxDegree1, then // we'll need to use the node with degree = maxDegree2. The answer in // general will be (maxDegree1 + maxDegree2), but if the two nodes that // we're considering are connected, then we'll have to subtract 1. const int edgeCount = getEdgeCount(roads, degrees, maxDegree1, maxDegree2) + getEdgeCount(roads, degrees, maxDegree2, maxDegree1); return maxDegree1 + maxDegree2 - (countMaxDegree2 == edgeCount ? 1 : 0); } else { // Case 2: If there are more than one node with degree = maxDegree1, // then we can consider maxDegree1 twice, and we don't need to use // maxDegree2. The answer in general will be 2 * maxDegree1, but if the // two nodes that we're considering are connected, then we'll have to // subtract 1. const int edgeCount = getEdgeCount(roads, degrees, maxDegree1, maxDegree1); const int maxPossibleEdgeCount = countMaxDegree1 * (countMaxDegree1 - 1) / 2; return 2 * maxDegree1 - (maxPossibleEdgeCount == edgeCount ? 1 : 0); } } private: // Returns the number of edges (u, v) where degress[u] == degreeU and // degrees[v] == degreeV. int getEdgeCount(const vector>& roads, const vector& degrees, int degreeU, int degreeV) { int edgeCount = 0; for (const vector& road : roads) { const int u = road; const int v = road; if (degrees[u] == degreeU && degrees[v] == degreeV) ++edgeCount; } return edgeCount; } }; 
  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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 class Solution { public int maximalNetworkRank(int n, int[][] roads) { int[] degrees = new int[n]; for (int[] road : roads) { final int u = road; final int v = road; ++degrees[u]; ++degrees[v]; } // Find the first maximum and the second maximum degrees. int maxDegree1 = 0; int maxDegree2 = 0; for (final int degree : degrees) if (degree > maxDegree1) { maxDegree2 = maxDegree1; maxDegree1 = degree; } else if (degree > maxDegree2) { maxDegree2 = degree; } // There can be multiple nodes with the maxDegree1 or the maxDegree2. // Find the counts of such nodes. int countMaxDegree1 = 0; int countMaxDegree2 = 0; for (final int degree : degrees) if (degree == maxDegree1) ++countMaxDegree1; else if (degree == maxDegree2) ++countMaxDegree2; if (countMaxDegree1 == 1) { // Case 1: If there is only one node with degree = maxDegree1, then // we'll need to use the node with degree = maxDegree2. The answer in // general will be (maxDegree1 + maxDegree2), but if the two nodes that // we're considering are connected, then we'll have to subtract 1. final int edgeCount = getEdgeCount(roads, degrees, maxDegree1, maxDegree2) + getEdgeCount(roads, degrees, maxDegree2, maxDegree1); return maxDegree1 + maxDegree2 - (countMaxDegree2 == edgeCount ? 1 : 0); } else { // Case 2: If there are more than one node with degree = maxDegree1, // then we can consider maxDegree1 twice, and we don't need to use // maxDegree2. The answer in general will be 2 * maxDegree1, but if the // two nodes that we're considering are connected, then we'll have to // subtract 1. final int edgeCount = getEdgeCount(roads, degrees, maxDegree1, maxDegree1); final int maxPossibleEdgeCount = countMaxDegree1 * (countMaxDegree1 - 1) / 2; return 2 * maxDegree1 - (maxPossibleEdgeCount == edgeCount ? 1 : 0); } } // Returns the number of edges (u, v) where degress[u] == degreeU and // degrees[v] == degreeV. private int getEdgeCount(int[][] roads, int[] degrees, int degreeU, int degreeV) { int edgeCount = 0; for (int[] road : roads) { final int u = road; final int v = road; if (degrees[u] == degreeU && degrees[v] == degreeV) ++edgeCount; } return edgeCount; } } 
  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 49 50 51 52 53 54 55 56 class Solution: def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int: degrees =  * n for u, v in roads: degrees[u] += 1 degrees[v] += 1 # Find the first maximum and the second maximum degrees. maxDegree1 = 0 maxDegree2 = 0 for degree in degrees: if degree > maxDegree1: maxDegree2 = maxDegree1 maxDegree1 = degree elif degree > maxDegree2: maxDegree2 = degree # There can be multiple nodes with the maxDegree1 or the maxDegree2. # Find the counts of such nodes. countMaxDegree1 = 0 countMaxDegree2 = 0 for degree in degrees: if degree == maxDegree1: countMaxDegree1 += 1 elif degree == maxDegree2: countMaxDegree2 += 1 if countMaxDegree1 == 1: # Case 1: If there is only one node with degree = maxDegree1, then # we'll need to use the node with degree = maxDegree2. The answer in # general will be (maxDegree1 + maxDegree2), but if the two nodes that # we're considering are connected, then we'll have to subtract 1. edgeCount = self._getEdgeCount(roads, degrees, maxDegree1, maxDegree2) + \ self._getEdgeCount(roads, degrees, maxDegree2, maxDegree1) return maxDegree1 + maxDegree2 - (countMaxDegree2 == edgeCount) else: # Case 2: If there are more than one node with degree = maxDegree1, # then we can consider maxDegree1 twice, and we don't need to use # maxDegree2. The answer in general will be 2 * maxDegree1, but if the # two nodes that we're considering are connected, then we'll have to # subtract 1. edgeCount = self._getEdgeCount(roads, degrees, maxDegree1, maxDegree1) maxPossibleEdgeCount = countMaxDegree1 * (countMaxDegree1 - 1) // 2 return 2 * maxDegree1 - (maxPossibleEdgeCount == edgeCount) def _getEdgeCount(self, roads: List[List[int]], degrees: List[int], degreeU: int, degreeV: int) -> int: """ Returns the number of edges (u, v) where degress[u] == degreeU and degrees[v] == degreeV. """ edgeCount = 0 for u, v in roads: if degrees[u] == degreeU and degrees[v] == degreeV: edgeCount += 1 return edgeCount