Real O(N^2) Solution, base on Tarjan's algorithm
In a graph, if we remove one node from the graph, the graph becomes 2 or more graphs, we call it an articulation point.\n\n\nTarjan\'s algorithm is a classic al
In a graph, if we remove one node from the graph, the graph becomes 2 or more graphs, we call it an articulation point.\n![image](https://assets.leetcode.com/users/pjincz/image_1543399151.png)\n\nTarjan\'s algorithm is a classic algorithm to find all articulation points in O(N+V) time complex. N=nodes, V=edges.\n\nhttps://en.wikipedia.org/wiki/Biconnected_component\n\nBase on Tarjan\'s algorithm, we are not only want to known each articulation point, but also we are interested in new graphs after remove ap.\nWith this enhanced Tarjan\'s algorithm, we can easy to know how many nodes we can save after remove a special node:\nIf graph has 0 malware, we save 0.\nIf graph has 1 malware and n nodes, by remove the malware, we save n-1 nodes\nif graph has more than 1 malwares, by remove an articulation point, we split one graph to multi graphs. Each graphs without malware are saved.\n\nThis solution also can answer a stronger question: if we remove any node(walmare or normal) from the graph, how many nodes we can save.\n\nIn code: network = graph, node = vertex, subnet = graph if ap removed\n\n```\nstruct NodeInfo {\n    bool malware = false;\n    \n    int netid = -1;\n    vector<pair<int, int>> subnets;\n    \n    int parent = -1;\n    int depth = -1;\n    int low = -1;\n};\n\nclass Solution {\npublic:\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        m_graph = &graph;\n        m_networks.clear();\n        m_nodes.clear();\n        \n        m_nodes.resize(graph.size());\n        \n        for (int i : initial) {\n            m_nodes[i].malware = true;\n        }\n        \n        for (int i = 0; i < m_nodes.size(); ++i) {\n            if (m_nodes[i].netid != -1)\n                continue;\n            \n            auto x = dfs(i, 0, m_networks.size());\n            m_networks.push_back(x);\n        }\n        \n        // dump\n        /*\n        cout << "networks:" << endl;\n        for (auto n : m_networks) {\n            cout << "nodes: " << n.first << ", malwares: " << n.second << endl;\n        }\n        cout << endl;\n        \n        for (int i = 0; i < m_nodes.size(); ++i) {\n            cout << "i: " << i << ", ";\n            cout << "net: " << m_nodes[i].netid << ", ";\n            cout << "subnets: [";\n            for (auto sn : m_nodes[i].subnets) {\n                cout << "(" << sn.first << ", " << sn.second << "), ";\n            }\n            cout << "]" << endl;\n        }\n        cout << endl;*/\n        \n        int maxSaves = -1;\n        int maxIdx = -1;\n        for (int i = 0; i < m_nodes.size(); ++i) {\n            if (!m_nodes[i].malware)\n                continue;\n            int s = saves(m_nodes[i]);\n            if (s > maxSaves) {\n                maxSaves = s;\n                maxIdx = i;\n            }\n            //cout << i << ", " << s << endl;\n        }\n        \n        return maxIdx;\n    }\n    \n    pair<int, int> dfs(int i, int d, int netid) {\n        m_nodes[i].depth = d;\n        m_nodes[i].low = d;\n        m_nodes[i].netid = netid;\n        \n        pair<int, int> scaned(1, m_nodes[i].malware ? 1 : 0);\n        \n        for (int j = 0; j < m_graph->size(); ++j) {\n            if (j == i)\n                continue;\n            if (!(*m_graph)[i][j])\n                continue;\n            \n            if (m_nodes[j].depth < 0) {\n                m_nodes[j].parent = i;\n                auto x = dfs(j, d + 1, netid);\n                if (m_nodes[j].low >= m_nodes[i].depth) {\n                    m_nodes[i].subnets.push_back(x);\n                }\n                m_nodes[i].low = std::min(m_nodes[i].low, m_nodes[j].low);\n                \n                scaned.first += x.first;\n                scaned.second += x.second;\n            } else if (j != m_nodes[i].parent) {\n                m_nodes[i].low = std::min(m_nodes[i].low, m_nodes[j].depth);\n            }\n        }\n        \n        if (m_nodes[i].parent == -1) {\n            if (m_nodes[i].subnets.size())\n                m_nodes[i].subnets.pop_back();\n        }\n        \n        return scaned;\n    }\n    \n    int saves(NodeInfo & n) {\n        if (m_networks[n.netid].second == 0)\n            return 0;\n        \n        pair<int, int> lastSubnet = m_networks[n.netid];\n        lastSubnet.first -= 1;\n        lastSubnet.second -= n.malware ? 1 : 0;\n        \n        int count = 0;\n        for (auto & subnet : n.subnets) {\n            if (subnet.second == 0)\n                count += subnet.first;\n            lastSubnet.first -= subnet.first;\n            lastSubnet.second -= subnet.second;\n        }\n        if (lastSubnet.second == 0)\n            count += lastSubnet.first;\n        \n        return count;\n    }\n    \n    vector<vector<int>> * m_graph;\n    vector<pair<int, int>> m_networks; // <nodes in network, malwares in network>\n    vector<NodeInfo> m_nodes;\n};\n```
[]