2285. Maximum Total Importance of Roads Medium

1/**
2 * [2285] Maximum Total Importance of Roads
3 *
4 * You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.
5 * You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.
6 * You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.
7 * Return the maximum total importance of all roads possible after assigning the values optimally.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/07/ex1drawio.png" style="width: 290px; height: 215px;" />
11 * Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
12 * Output: 43
13 * Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
14 * - The road (0,1) has an importance of 2 + 4 = 6.
15 * - The road (1,2) has an importance of 4 + 5 = 9.
16 * - The road (2,3) has an importance of 5 + 3 = 8.
17 * - The road (0,2) has an importance of 2 + 5 = 7.
18 * - The road (1,3) has an importance of 4 + 3 = 7.
19 * - The road (2,4) has an importance of 5 + 1 = 6.
20 * The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
21 * It can be shown that we cannot obtain a greater total importance than 43.
22 * 
23 * Example 2:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/07/ex2drawio.png" style="width: 281px; height: 151px;" />
25 * Input: n = 5, roads = [[0,3],[2,4],[1,3]]
26 * Output: 20
27 * Explanation: The figure above shows the country and the assigned values of [4,3,2,5,1].
28 * - The road (0,3) has an importance of 4 + 5 = 9.
29 * - The road (2,4) has an importance of 2 + 1 = 3.
30 * - The road (1,3) has an importance of 3 + 5 = 8.
31 * The total importance of all roads is 9 + 3 + 8 = 20.
32 * It can be shown that we cannot obtain a greater total importance than 20.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	2 <= n <= 5 * 10^4
38 * 	1 <= roads.length <= 5 * 10^4
39 * 	roads[i].length == 2
40 * 	0 <= ai, bi <= n - 1
41 * 	ai != bi
42 * 	There are no duplicate roads.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/maximum-total-importance-of-roads/
48// discuss: https://leetcode.com/problems/maximum-total-importance-of-roads/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn maximum_importance(n: i32, roads: Vec<Vec<i32>>) -> i64 {
54        
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2285() {
66    }
67}
68