Remove One Infected Vertex and Its Edges to Limit Malware

### Problem An undirected network is given by adjacency matrix `graph`, with infected seeds in `initial`. Infection repeatedly crosses an edge from an infected node to an uninfected one. Choose exactly one initial node and remove that vertex and all its incident edges completely. Return the removed label minimizing the final number infected among remaining nodes, breaking ties by smallest label. ```cpp class Solution { public: int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial); }; ``` ### Examples **Example 1:** ```text Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,2] Output: 2 Explanation: Removing2 leaves only0 and1 infected;3 is isolated. Removing0 lets seed2 infect1 and3, for three infected nodes. ``` **Example 2:** ```text Input: graph = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], initial = [3,1] Output: 1 Explanation: Either removal leaves one isolated seed infected, so choose the smaller label. ``` ### Constraints - `n == graph.length == graph[i].length`; `2 <= n <= 300`. - Entries are0 or1; graph is symmetric and every diagonal entry is1. - `1 <= initial.length < n`. - Initial labels are unique and lie between0 and n-1. ### Contract considerations Initial contains fewer than n nodes. Its order is arbitrary and its labels are unique. The requested label is uniquely determined by the smallest-index tie rule. ```hint Read the boundary condition Consider components after excluding every initial seed; which seeds can still infect each component? ``` ### Boundary reminders Initial contains fewer than n nodes. Its order is arbitrary and its labels are unique. The requested label is uniquely determined by the smallest-index tie rule.