DFS || Explanation with detailed steps || Simple (BEST SOLUTION)
\n# Approach\nThe solution simulates removing each initially infected node, uses DFS to count the resulting spread of malware, and identifies the node whose rem
\n# Approach\n**The solution simulates removing each initially infected node, uses DFS to count the resulting spread of malware, and identifies the node whose removal minimizes the spread while preferring the smallest index in case of ties.**\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n\n# Code\n```\nclass Solution {\npublic:\n    // Graph representation\n    vector<vector<int>> g;\n\n    // Depth-first search (DFS) to count nodes in the connected component excluding a specific node\n    int dfs(int nn, int nottotake, vector<int>& vis) {\n        vis[nn] = 1; // Mark the current node as visited\n        int sum = 1; // Initialize count for the current node\n        // Traverse all adjacent nodes\n        for (auto adj : g[nn]) {\n            // If the node is not visited and is not the node to exclude, continue DFS\n            if (!vis[adj] && adj != nottotake) {\n                sum += dfs(adj, nottotake, vis); // Add the count of connected nodes\n            }\n        }\n        return sum; // Return the total count of nodes in this connected component\n    }\n\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        int n = graph.size(); // Number of nodes in the graph\n        g.resize(n); // Resize the graph to fit the number of nodes\n\n        // Build the adjacency list from the adjacency matrix\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (graph[i][j]) {\n                    g[i].push_back(j); // Add an edge between node i and node j\n                }\n            }\n        }\n\n        unordered_map<int, int> mp; // Map to count occurrences of initially infected nodes\n        for (auto i : initial)\n            mp[i]++; // Increment the count for each initially infected node\n\n        int mini = 1e8, ans; // Initialize minimum infected count and answer node\n\n        // Iterate over each initially infected node to simulate removal\n        for (auto ele : initial) {\n            int cnt = 1; // Initialize infected count\n            vector<int> vis(n, 0); // Visited array to keep track of visited nodes\n\n            // Count the number of nodes that would be infected if \'ele\' is removed\n            for (int i = 0; i < n; i++) {\n                if (!vis[i] && mp[i] && i != ele)\n                    cnt += dfs(i, ele, vis); // Perform DFS to count infected nodes\n            }\n\n            // Update the answer if the current count is less than the minimum found so far\n            if (cnt < mini) {\n                mini = cnt;\n                ans = ele;\n            }\n            // If the count is the same, choose the node with the smaller index\n            else if (cnt == mini) {\n                ans = min(ans, ele);\n            }\n        }\n\n        return ans; // Return the node that should be removed to minimize the malware spread\n    }\n};\n\n```
['Depth-First Search', 'C++']