1615. Maximal Network Rank Medium

1/**
2 * [1615] Maximal Network Rank
3 *
4 * 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.
5 * 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.
6 * The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
7 * Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/21/ex1.png" style="width: 292px; height: 172px;" />
11 * 
12 * Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
13 * Output: 4
14 * 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.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/21/ex2.png" style="width: 292px; height: 172px;" />
18 * 
19 * Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
20 * Output: 5
21 * Explanation: There are 5 roads that are connected to cities 1 or 2.
22 * 
23 * Example 3:
24 * 
25 * Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
26 * Output: 5
27 * Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	2 <= n <= 100
33 * 	0 <= roads.length <= n * (n - 1) / 2
34 * 	roads[i].length == 2
35 * 	0 <= ai, bi <= n-1
36 * 	ai != bi
37 * 	Each pair of cities has at most one road connecting them.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/maximal-network-rank/
43// discuss: https://leetcode.com/problems/maximal-network-rank/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn maximal_network_rank(n: i32, roads: Vec<Vec<i32>>) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_1615() {
61    }
62}
63