2497. Maximum Star Sum of a Graph Medium

1/**
2 * [2497] Maximum Star Sum of a Graph
3 *
4 * There is an undirected graph consisting of n nodes numbered from 0 to n - 1. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the i^th node.
5 * You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
6 * A star graph is a subgraph of the given graph having a center node containing 0 or more neighbors. In other words, it is a subset of edges of the given graph such that there exists a common node for all edges.
7 * The image below shows star graphs with 3 and 4 neighbors respectively, centered at the blue node.
8 * <img alt="" src="https://assets.leetcode.com/uploads/2022/11/07/max-star-sum-descdrawio.png" style="width: 400px; height: 179px;" />
9 * The star sum is the sum of the values of all the nodes present in the star graph.
10 * Given an integer k, return the maximum star sum of a star graph containing at most k edges.
11 *  
12 * <strong class="example">Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2022/11/07/max-star-sum-example1drawio.png" style="width: 300px; height: 291px;" />
14 * Input: vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
15 * Output: 16
16 * Explanation: The above diagram represents the input graph.
17 * The star graph with the maximum star sum is denoted by blue. It is centered at 3 and includes its neighbors 1 and 4.
18 * It can be shown it is not possible to get a star graph with a sum greater than 16.
19 * 
20 * <strong class="example">Example 2:
21 * 
22 * Input: vals = [-5], edges = [], k = 0
23 * Output: -5
24 * Explanation: There is only one possible star graph, which is node 0 itself.
25 * Hence, we return -5.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	n == vals.length
31 * 	1 <= n <= 10^5
32 * 	-10^4 <= vals[i] <= 10^4
33 * 	0 <= edges.length <= min(n * (n - 1) / 2, 10^5)
34 * 	edges[i].length == 2
35 * 	0 <= ai, bi <= n - 1
36 * 	ai != bi
37 * 	0 <= k <= n - 1
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/maximum-star-sum-of-a-graph/
43// discuss: https://leetcode.com/problems/maximum-star-sum-of-a-graph/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn max_star_sum(vals: Vec<i32>, edges: Vec<Vec<i32>>, k: 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_2497() {
61    }
62}
63