Best C++ Solution using vector and set(in desc order)
Intuition\nThe problem involves finding the maximum \u201Cstar sum\u201D in a graph. A \u201Cstar\u201D centered at a node i includes the node itself and at mos
# Intuition\nThe problem involves finding the maximum \u201Cstar sum\u201D in a graph. A \u201Cstar\u201D centered at a node i includes the node itself and at most k of its neighboring nodes. The sum is calculated by adding the value of the node i and the values of the k largest (non-negative) neighboring nodes connected to it.\n\n# Approach\n**1.Graph Representation:**\n- First, the graph is represented using an adjacency list. Each node i is associated with a set of pairs where each pair contains a neighbor\u2019s value and the neighbor\u2019s index. The set is ordered in descending order of values using the greater comparator. This allows easy access to the top k neighbors with the highest values.\n\n**2.\tBuilding the Adjacency List:**\n- For each edge in the graph, the corresponding nodes are connected by inserting their values and indices into each other\u2019s set.\n\n**3.\tCalculating the Star Sum:**\n\n- For each node i, the initial sum starts with its own value (vals[i]).\n- The code then iterates over the sorted set of neighboring nodes and adds their values to the current sum. This is done for up to k neighbors or until a negative value is encountered, at which point the loop breaks (since adding negative values would decrease the sum).\n- The maximum sum found across all nodes is returned as the result.\n\n\n\n# Complexity\n- Time complexity:\nThe overall time complexity is **O(m log n + n * k log n),** which simplifies to O(n * k log n) if m and n are of the same order.\n\n- Space complexity:\nO(n * k)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {\n        int n = vals.size();\n        vector<set<pair<int, int>, greater<pair<int, int>>>> adj(n);\n        for(auto it: edges){\n            adj[it[0]].insert({vals[it[1]], it[1]});\n            adj[it[1]].insert({vals[it[0]], it[0]});\n        }\n\n        int maxSum = INT_MIN;\n        for(int i=0; i<n; i++){\n            int currSum = vals[i];\n            int kt = k;\n            for(auto nbr: adj[i]){\n\n                if(kt==0 || vals[nbr.second] < 0)    break;\n                currSum += vals[nbr.second];\n                kt--;\n            }\n            maxSum = max(maxSum, currSum);\n        }\n        return maxSum;\n    }\n};\n```
['Ordered Set', 'C++']