LeetCode 1615. Maximal Network Rank

, , , ,

Question

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 connected 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.

Constraints:

  • 2 <= n <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 2
  • 0 <= ai, bi <= n-1
  • ai != bi
  • Each pair of cities has at most one road connecting them.

Example

1
2
3
4
5
6
7
8
9
10
11
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Solution

通过题目理解，发现该题是一个Graph题目，然后通过找到其中一个edge，从这两个点看最多可以走多少个点。一开始觉得是connected component的题目，但是仔细一想，结果很大程度取决于选定的edge，所以并不是看全部形成的连通图。思考到这里，发现自己可以遍历不同的edge，之后看每个edge形成的最大情况。下面的解法比较巧妙运用了上面的想法，先用count数组记录与当前点连接的情况，并且标记有哪些点之间是可以连通的。之后就通过遍历不同的点，去计算有多少个可以连通的点，但是这里需要注意的是，如果两个点之间是连通的，那么之前计算则会有重复的计数，需要减去1。

Code

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
package com.leetcode.graph;

/**
 * @Date: 10/11/2020
 * @Description: Graph, Count
 **/
public class _1615_Maximal_Network_Rank {
    public int maximalNetworkRank(int n, int[][] roads) {
        boolean[][] connected = new boolean[n][n];
        int[] count = new int[n];
        for (int[] road : roads) {
            count[road[0]]++;
            count[road[1]]++;
            connected[road[0]][road[1]] = true;
            connected[road[1]][road[0]] = true;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                res = Math.max(res, count[i] + count[j] - (connected[i][j] ? 1 : 0));
            }
        }
        return res;
    }
}

Reference