Question

Formatted question description: https://leetcode.ca/all/1615.html

 1615. Maximal Network Rank


 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.


 Example 1:

 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.


 Example 2:

 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.


 Example 3:

 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.


 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.

Algorithm

Essentially, it is looking for the largest network rank between two points in the input. This is a graph theory problem. Note that each given edge is undirected, so for two points on an edge, their ranks are each +1. The idea is to first use an array of edges to record the rank of each point. Each time an edge is encountered, the ranks of the points at both ends of the edge are each +1; at the same time, we need a two-dimensional adjacency matrix adj, here I Choose to use boolean, because we only need to record whether the two points are adjacent points.

After we traverse the roads array, we can count both the edges array and the adj matrix. After that, we will use two for loops to traverse these N points and look at the rank sum between each two different points. Note that if two points can be directly connected, they will be true in the adjacency matrix adj, and the rank needs to be reduced by one.

Code

Java

    class Solution {
        public int maximalNetworkRank(int n, int[][] roads) {
            boolean[][] connected = new boolean[n][n];
            int[] cnts = new int[n];
            for (int[] r : roads) {
                cnts[r[0]]++;
                cnts[r[1]]++;
                connected[r[0]][r[1]] = true;
                connected[r[1]][r[0]] = true;  // cache if i and j directly connected
            }
            int res = 0;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                    res = Math.max(res, cnts[i] + cnts[j] - (connected[i][j] ? 1 : 0));  // loop all pairs
            return res;
        }

    }

Java

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        for (int[] road : roads) {
            int city0 = road[0], city1 = road[1];
            Set<Integer> set0 = map.getOrDefault(city0, new HashSet<Integer>());
            Set<Integer> set1 = map.getOrDefault(city1, new HashSet<Integer>());
            set0.add(city1);
            set1.add(city0);
            map.put(city0, set0);
            map.put(city1, set1);
        }
        int maxRank = 0;
        for (int i = 0; i < n; i++) {
            Set<Integer> set0 = map.getOrDefault(i, new HashSet<Integer>());
            for (int j = i + 1; j < n; j++) {
                Set<Integer> set1 = map.getOrDefault(j, new HashSet<Integer>());
                int rank = set0.size() + set1.size();
                if (set0.contains(j))
                    rank--;
                maxRank = Math.max(maxRank, rank);
            }
        }
        return maxRank;
    }
}

All Problems

All Solutions