Simple Iterative BFS Solution: O(k * n^2)
Intuition\nRemoving a node is equivalent to skipping it in graph algorithms.\n\n# Approach\n\n- For each initial node that can be skipped:\n  - Skip it and find
# Intuition\nRemoving a node is equivalent to skipping it in graph algorithms.\n\n# Approach\n\n- For each initial node that can be skipped:\n  - Skip it and find the number of infected nodes:\n    - Perform BFS starting from all initially infected nodes except the one to be skipped. \n        - Note: BFS algorithm should skip the node as well.\n    - Number of Infected nodes = Number of visited nodes \n  - If Number of infected noes is minimum, this is the node we should skip.\n\nReturn the node skipping which yielded least number of infected nodes.\n\n\n# Complexity\n\n### Time Complexity\n\nLet k be the number of initially infected nodes, n be the total number of nodes.\n\nFor each initial node we perform BFS. \n\n= O(k) * O(V + E)\n= O(k) * O(n + n^2)\n= **O(k * n^2)**\n\n### Space complexity:\n\n- Create an adjacency list => O(n^2)\n- Visited Vector and queue for bfs => O(n) and O(n)\n\n= **O(n^2)**\n\n\n# Code\n```\nclass Solution {\n   public:\n    // Perfroms BFS starting from all initially infected nodes except the one to be skipped\n    // BFS too skips the node to be skipped\n    // Returns the total number of visited (infected) nodes\n    // O(v + e) -> O(n^2)\n    int totalInfected(vector<vector<int>>& adj_list, vector<int>& initial, int to_skip) {\n        int n = adj_list.size();\n\n        int num_visited_nodes = 0;\n        vector<bool> visited(n, 0);\n\n        // Pushes the node into queue, marks it as visited, and increases the number of visited nodes\n        auto visit_node = [&](queue<int>& q, int node) {\n            q.push(node);\n            visited[node] = true;\n            num_visited_nodes++;\n        };\n\n        // DO BFS starting from all initially infected, unvisted and not to be skipped nodes\n        for (const int& start : initial) {\n            if (start == to_skip || visited[start]) {\n                continue;\n            }\n\n            queue<int> q;\n            visit_node(q, start);\n            while (!q.empty()) {\n                int front = q.front();\n                q.pop();\n                for (const int& nbr : adj_list[front]) {\n                    if (nbr == to_skip) {\n                        continue;\n                    }\n\n                    if (!visited[nbr]) {\n                        visit_node(q, nbr);\n                    }\n                }\n            }\n        }\n        return num_visited_nodes;\n    }\n\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        // Convert the graph from adj matrix to adj list (lower time complexity for sparse graphs)\n        vector<vector<int>> adj_list(graph.size(), vector<int>());\n        for (int i = 0; i < graph.size(); i++) {\n            for (int j = 0; j < graph.size(); j++) {\n                if (graph[i][j]) {\n                    adj_list[i].push_back(j);\n                }\n            }\n        }\n\n        // Iteratively skip each starting node and find how many nodes will be infected using bfs\n        // Keep track of the minimum number of infected nodes and the node to be removed\n        int node_to_be_removed = -1;\n        int minimum_infection_so_far = graph.size() + 1;\n        for (const int& skip_node : initial) {\n            int infected_nodes = totalInfected(adj_list, initial, skip_node);\n\n            if (infected_nodes < minimum_infection_so_far) {\n                minimum_infection_so_far = infected_nodes;\n                node_to_be_removed = skip_node;\n            } else if (infected_nodes == minimum_infection_so_far && skip_node < node_to_be_removed) {\n                node_to_be_removed = skip_node;\n            }\n        }\n        return node_to_be_removed;\n    }\n};\n```
['Breadth-First Search', 'C++']