<p>You are given a network of <code>n</code> nodes represented as an <code>n x n</code> adjacency matrix <code>graph</code>, where the <code>i<sup>th</sup></code> node is directly connected to the <code>j<sup>th</sup></code> node if <code>graph[i][j] == 1</code>.</p>

<p>Some nodes <code>initial</code> are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.</p>

<p>Suppose <code>M(initial)</code> is the final number of nodes infected with malware in the entire network after the spread of malware stops.</p>

<p>We will remove <strong>exactly one node</strong> from <code>initial</code>, <strong>completely removing it and any connections from this node to any other node</strong>.</p>

<p>Return the node that, if removed, would minimize <code>M(initial)</code>. If multiple nodes could be removed to minimize <code>M(initial)</code>, return such a node with <strong>the smallest index</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
<strong>Output:</strong> 0
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
<strong>Output:</strong> 1
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
<strong>Output:</strong> 1
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>n == graph[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 300</code></li>
	<li><code>graph[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>graph[i][j] == graph[j][i]</code></li>
	<li><code>graph[i][i] == 1</code></li>
	<li><code>1 &lt;= initial.length &lt;&nbsp;n</code></li>
	<li><code>0 &lt;= initial[i] &lt;= n - 1</code></li>
	<li>All the integers in <code>initial</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
   public:
    // Perfroms BFS starting from all initially infected nodes except the one to be skipped
    // BFS too skips the node to be skipped
    // Returns the total number of visited (infected) nodes
    // O(v + e) -> O(n^2)
    int totalInfected(vector<vector<int>>& adj_list, vector<int>& initial, int to_skip) {
        int n = adj_list.size();

        int num_visited_nodes = 0;
        vector<bool> visited(n, 0);

        // Pushes the node into queue, marks it as visited, and increases the number of visited nodes
        auto visit_node = [&](queue<int>& q, int node) {
            q.push(node);
            visited[node] = true;
            num_visited_nodes++;
        };

        // DO BFS starting from all initially infected, unvisted and not to be skipped nodes
        for (const int& start : initial) {
            if (start == to_skip || visited[start]) {
                continue;
            }

            queue<int> q;
            visit_node(q, start);
            while (!q.empty()) {
                int front = q.front();
                q.pop();
                for (const int& nbr : adj_list[front]) {
                    if (nbr == to_skip) {
                        continue;
                    }

                    if (!visited[nbr]) {
                        visit_node(q, nbr);
                    }
                }
            }
        }
        return num_visited_nodes;
    }

    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        // Convert the graph from adj matrix to adj list (lower time complexity for sparse graphs)
        vector<vector<int>> adj_list(graph.size(), vector<int>());
        for (int i = 0; i < graph.size(); i++) {
            for (int j = 0; j < graph.size(); j++) {
                if (graph[i][j]) {
                    adj_list[i].push_back(j);
                }
            }
        }

        // Iteratively skip each starting node and find how many nodes will be infected using bfs
        // Keep track of the minimum number of infected nodes and the node to be removed
        int node_to_be_removed = -1;
        int minimum_infection_so_far = graph.size() + 1;
        for (const int& skip_node : initial) {
            int infected_nodes = totalInfected(adj_list, initial, skip_node);

            if (infected_nodes < minimum_infection_so_far) {
                minimum_infection_so_far = infected_nodes;
                node_to_be_removed = skip_node;
            } else if (infected_nodes == minimum_infection_so_far && skip_node < node_to_be_removed) {
                node_to_be_removed = skip_node;
            }
        }
        return node_to_be_removed;
    }
};
50200