Skip to content

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
class Solution {
 public:
  int maximalNetworkRank(int n, vector<vector<int>>& roads) {
    vector<int> degrees(n);

    for (const vector<int>& road : roads) {
      const int u = road[0];
      const int v = road[1];
      ++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 `maxDegree1` or `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) {
      // 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 {
      // 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<vector<int>>& roads, const vector<int>& degrees,
                   int degreeU, int degreeV) {
    int edgeCount = 0;
    for (const vector<int>& road : roads) {
      const int u = road[0];
      const int v = road[1];
      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
class Solution {
  public int maximalNetworkRank(int n, int[][] roads) {
    int[] degrees = new int[n];

    for (int[] road : roads) {
      final int u = road[0];
      final int v = road[1];
      ++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 `maxDegree1` or `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) {
      // 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 {
      // 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[0];
      final int v = road[1];
      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
class Solution:
  def maximalNetworkRank(self, n: int, roads: list[list[int]]) -> int:
    degrees = [0] * 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 `maxDegree1` or `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:
      # 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:
      # 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