DP on Graphs/Tree with Re-Rooting | C++ | O(n^2) Time
Idea is based on DP on Trees/Graphs with Re-rooting.\n\nApproach: We view each connected graph component as a tree (using DFS Tree), then we apply the conepts o
Idea is based on DP on Trees/Graphs with Re-rooting.\n\nApproach: We view each connected graph component as a tree (using DFS Tree), then we apply the conepts of DP on Tree with Re-rooting to solve the problem. \n\nStep1: Find all articulation points in the graph.\n\nStep2: Perform DFS and update the values of number of nodes in subtree of each node and infected nodes in subtree of each node.\n\nStep3: Perform re-rooting using another DFS function (dfs2) and using the results of parent node, update the results for children node.\n\nStep4: Check for removal condition on (1) Infected Node  AND (2) If the node is the **ONLY** infected node in this connected component OR the node is an articulation point.\n\n```\nclass Solution {\npublic:\n    set<int> articulation;\n    vector<bool> vis;\n    vector<vector<int>> adj;\n    vector<int> tin, low;\n    int dfs_timer;\n    int n;\n    void dfs_articulation(int v, int par = -1) {\n        vis[v] = 1;\n        tin[v] = low[v] = dfs_timer++;\n        int children = 0;\n        for (auto& child : adj[v]) {\n            if (child == par)\n                continue;\n            if (!vis[child]) {\n                dfs_articulation(child, v);\n                low[v] = min(low[v], low[child]);\n                if (low[child] >= tin[v] && par != -1)\n                    articulation.insert(v);\n                children++;\n            } else\n                low[v] = min(low[v], tin[child]);\n        }\n        if (par == -1 && children >= 2)\n            articulation.insert(v);\n    }\n\n    void find_cutpoints() {\n        dfs_timer = 0;\n        vis.assign(n, false);\n        tin.assign(n, -1);\n        low.assign(n, -1);\n        for (int i = 0; i < n; ++i)\n            if (!vis[i])\n                dfs_articulation(i);\n    }\n\n    vector<int> subRootedNodes, components, infectedNodes;\n    vector<bool> isInfectedNode;\n    int answer, total, answerNode;\n    void dfs1(int node) {\n        vis[node] = 1;\n        subRootedNodes[node] = 1;\n        if (isInfectedNode[node])\n            infectedNodes[node] = 1;\n\n        for (auto& child : adj[node]) {\n            if (!vis[child]) {\n                dfs1(child);\n                infectedNodes[node] += infectedNodes[child];\n                subRootedNodes[node] += subRootedNodes[child];\n            }\n        }\n    }\n\n    void dfs2(int node, int x, int topNodes, int topInfectedNodes, bool flag) {\n        vis[node] = 1;\n        int currentInfected = 0;\n        if (topInfectedNodes > 0)\n            currentInfected = topNodes;\n\n        for (auto& child : adj[node]) {\n            if (!vis[child]) {\n                dfs2(child, x,\n                     topNodes + subRootedNodes[node] - subRootedNodes[child],\n                     topInfectedNodes + infectedNodes[node] -\n                         infectedNodes[child],\n                     flag);\n                if (infectedNodes[child])\n                    currentInfected += subRootedNodes[child];\n            }\n        }\n        if (isInfectedNode[node] &&\n            (flag || articulation.find(node) != articulation.end())) {\n            if (answer > total - x + currentInfected + 1) {\n                answer = total - x + currentInfected + 1;\n                answerNode = node;\n            }\n            if (answer == total - x + currentInfected + 1) {\n                answerNode = min(answerNode, node);\n            }\n        }\n    }\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        n = graph.size();\n        adj.assign(n, vector<int>(0));\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (graph[i][j] && i != j) {\n                    adj[i].push_back(j);\n                    adj[j].push_back(i);\n                }\n            }\n        }\n        isInfectedNode.assign(n, 0);\n        subRootedNodes.assign(n, 0);\n        infectedNodes.assign(n, 0);\n        components.assign(n, 0);\n\n        answerNode = n;\n        for (auto inf : initial)\n            isInfectedNode[inf] = 1, answerNode = min(answerNode, inf);\n        cout << answerNode << endl;\n        find_cutpoints();\n\n        vis.assign(n, 0);\n        total = 0;\n        for (int i = 0; i < n; i++) {\n            if (!vis[i]) {\n                dfs1(i);\n                total += (infectedNodes[i] > 0 ? subRootedNodes[i] : 0);\n            }\n        }\n\n        vis.assign(n, 0);\n        answer = total;\n        bool flag = 0;\n        for (int i = 0; i < n; i++) {\n            if (!vis[i]) {\n                int currentInfectedNodes =\n                    (infectedNodes[i] > 0 ? subRootedNodes[i] : 0);\n                if (infectedNodes[i] == 1)\n                    flag = 1;\n                dfs2(i, currentInfectedNodes, 0, 0, flag);\n            }\n        }\n        return answerNode;\n    }\n};\n```
['C++']