-
Notifications
You must be signed in to change notification settings - Fork 2
/
MaximalNetworkRank.java
72 lines (65 loc) · 2.34 KB
/
MaximalNetworkRank.java
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
package Leetcode;
/**
* @author kalpak
*
* 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.
*
*/
public class MaximalNetworkRank {
public static int maximalNetworkRank(int n, int[][] roads) {
int result = 0;
int[] count = new int[n];
boolean[][] isConnectedDirectly = new boolean[n][n];
for(int[] road : roads) {
count[road[0]]++;
count[road[1]]++;
isConnectedDirectly[road[0]][road[1]] = true;
isConnectedDirectly[road[1]][road[0]] = true;
}
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
result = Math.max(result, count[i] + count[j] - (isConnectedDirectly[i][j] == true ? 1 : 0)) ;
}
}
return result;
}
public static void main(String[] args) {
int[][] roads = new int[][]{{0,1},{0,3},{1,2},{1,3},{2,3},{2,4}};
System.out.println("The maximum rank of the network is : " + maximalNetworkRank(5, roads));
}
}