Choose One Initial Infection to Remove from an Undirected Network
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
In the undirected adjacency matrix `graph`, infection spreads across every edge until no further nodes can become infected. Remove exactly one node label from the initially infected set `initial`, leaving that node and all graph edges in place. Return the label whose removal minimizes the final infected count; break ties by the smallest label. A removed initial seed may still become infected from another seed.
```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,0,0],[0,0,1,0],[0,0,0,1]], initial = [0,2]
Output: 0
Explanation: Removing seed0 saves its two-node component; removing2 saves only one node.
```
**Example 2:**
```text
Input: graph = [[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]], initial = [3,1]
Output: 1
Explanation: Either remaining seed infects all four nodes, so choose the smaller removed 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
The matrix is symmetric with diagonal ones. The order of initial is not guaranteed sorted.
```hint Read the boundary condition
In an undirected component, does the final infection depend on how many seeds remain or only on whether any remain?
```
### Boundary reminders
The matrix is symmetric with diagonal ones. The order of initial is not guaranteed sorted.
Overview: Choose One Initial Infection to Remove from an Undirected Network. In the undirected adjacency matrix graph, infection spreads across every edge until no further nodes can become infected.