C++ Block Cut Tree + Sibling DP
Yeet funny data structure at problem and call it a day.\n\nhttps://en.wikipedia.org/wiki/Biconnected_component#Block-cut_tree\n\nAny graph can be decomposed int
Yeet funny data structure at problem and call it a day.\n\nhttps://en.wikipedia.org/wiki/Biconnected_component#Block-cut_tree\n\nAny graph can be decomposed into a tree made of nodes representing biconnected components, and nodes representing articulation points.\nArticulation points are nodes that are part of multiple biconnected components, so in the block-cut tree, there are edges between articulation points and their corresponding biconnected components.\nWe can find all biconnected components in `O(V + E)` with Tarjan\'s algorithm.\nIf you want a good framework for understanding this algorithm, this blog post about the DFS tree is very helpful: https://codeforces.com/blog/entry/68138.\n\nOnce we have this tree, imagine rerooting the tree at a malware node.\nThere are two cases in which removing the malware node saves more nodes.\nIf it\'s an articulation point, every child\'s subtree without malware will be saved.\nIf the node is the only malware node in the entire connected component, the whole connected component is saved.\n\nWe can figure out these subtree aggregates by using sibling dp.\nFor some node `i`, it has a list of edges `adj[i]`.\nWe define a memoized function `suffix_agg(i, j)` as using `i` to be the root of the tree, and returns the aggregate over the subtrees rooted at `adj[i][j]`, `adj[i][j+1]`, `adj[i][j+2]`, ...\nWe also define `prefix_agg(i, j)` similarly.\nI like to think about prefixes as exclusive intervals, so the aggregate is over `adj[i][0], ..., adj[i][j - 1]`.\nIt was also convenient to make `prefix_agg` exclude the root `i`, and `suffix_agg` include the root `i`.\nThen, with `ei = adj[i][j]` and `ej` is the index such that `adj[ei][ej] = i`, we have `suffix_agg(i, j) = suffix_agg(i, j + 1) + prefix_agg(ei, ej) + suffix_agg(ei, ej + 1)`, and `prefix_agg(i, j + 1) = prefix_agg(i, j) + prefix_agg(ei, ej) + suffix_agg(ei, ej + 1)`.\nAll of these subproblems operate on smaller subtrees, so we don\'t get infinite recursion.\nSince we\'re working on a tree, `E = O(V)`.\nThere are `O(V)` states, and each state does a constant number of calls to subproblems, so the runtime for this dp is `O(V)`.\n\nOnce we have our subtree aggregates for number of malware nodes and total node count in a subtree, `malware_suffix_agg[i][0]` will tell us the total number of malware nodes in the connected component.\nIf it\'s equal to `1`, then `count_suffix_agg[i][0]` nodes are saved.\nOtherwise, if the malware node is an articulation point, `malware_suffix_agg[i][j] - malware_suffix_agg[i][j + 1]` will tell us if the disconnected subtree has no malware, and if it doesn\'t have malware, then an additional `count_suffix_agg[i][j] - count_suffix_agg[i][j + 1]` nodes are saved.\n\nAll in all, this solution uses some niche data structures and algorithms, but if you treat them as black boxes, their application to this problem is fairly straightforward.\n\n---\n\n```cpp\n//#define DEBUG\nclass Solution {\npublic:\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        int n = graph.size();\n        for (int i = 0; i < n; ++i) {\n            auto& node = graph[i];\n            int adjidx = 0;\n            for (int j = 0; j < n; ++j) {\n                if (i == j) continue;\n                if (node[j]) {\n                    node[adjidx++] = j;\n                }\n            }\n            node.resize(adjidx);\n        }\n#ifdef DEBUG\n        for (int i = 0; i < n; ++i) {\n            std::cout << "adj " << i << \':\';\n            for (auto& e : graph[i]) {\n                std::cout << \' \' << e;\n            }\n            std::cout << std::endl;\n        }\n#endif\n        std::vector<std::vector<int>> bct;\n        std::vector<int> bct_node_size;\n        std::vector<int> bct_rep(n, -1);\n        std::vector<int> bcc_stack;\n        using it_t = decltype(bcc_stack)::iterator;\n        const auto found_bcc = [&](it_t beg, it_t end){\n#ifdef DEBUG\n            std::cout << "found bcc:";\n            for (auto it = beg; it != end; ++it) std::cout << \' \' << *it;\n            std::cout << std::endl;\n#endif\n            int bcc = bct.size();\n            bct.emplace_back();\n            bct_node_size.emplace_back();\n            for (auto it = beg; it != end; ++it) {\n                auto& rep = bct_rep[*it];\n                if (rep < 0) {\n                    ++bct_node_size[bcc];\n                    rep = bcc;\n                    continue;\n                }\n                if (bct_node_size[rep] >= 0) {\n                    int artic = bct.size();\n                    bct.push_back({rep});\n                    bct_node_size.push_back(-1);\n                    bct[rep].push_back(artic);\n                    --bct_node_size[rep];\n                    rep = artic;\n                }\n                bct[bcc].push_back(rep);\n                bct[rep].push_back(bcc);\n            }\n        };\n        std::vector<int> born(n);\n        int time = 0;\n        const std::function<int(int, int)> bcc_dfs = [&](int idx, int par){\n            int eldest = born[idx] = ++time;\n            for (int e : graph[idx]) {\n                if (e == par) continue;\n                if (born[e]) {\n                    if (born[e] > born[idx]) continue;\n                    eldest = std::min(eldest, born[e]);\n                } else {\n                    int stack_pos = bcc_stack.size();\n                    int elder = bcc_dfs(e, idx);\n                    if (elder >= born[idx]) {\n                        bcc_stack.push_back(idx);\n                        found_bcc(bcc_stack.begin() + stack_pos, bcc_stack.end());\n                        bcc_stack.resize(stack_pos);\n                    } else {\n                        eldest = std::min(eldest, elder);\n                    }\n                }\n            }\n            if (eldest <= born[idx]) {\n                bcc_stack.push_back(idx);\n            }\n            return eldest;\n        };\n        for (int i = 0; i < n; ++i) {\n            if (!born[i]) bcc_dfs(i, -1);\n        }\n        int m = bct.size();\n#ifdef DEBUG\n        for (int i = 0; i < n; ++i) {\n            std::cout << "rep " << i << ": " << bct_rep[i] << std::endl;\n        }\n        for (int i = 0; i < m; ++i) {\n            std::cout << "bct " << i << \'(\' << bct_node_size[i] << "):";\n            for (auto& e : bct[i]) {\n                std::cout << \' \' << e;\n            }\n            std::cout << std::endl;\n        }\n#endif\n        std::vector<std::unordered_map<int, int>> bct_lookup(m);\n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < bct[i].size(); ++j) {\n                bct_lookup[i][bct[i][j]] = j;\n            }\n        }\n        std::vector<std::vector<int>> bct_mal_suf_dp(m);\n        std::vector<std::vector<int>> bct_mal_pre_dp(m);\n        std::vector<std::vector<int>> bct_count_suf_dp(m);\n        std::vector<std::vector<int>> bct_count_pre_dp(m);\n        for (int i = 0; i < m; ++i) {\n            bct_count_pre_dp[i].assign(bct[i].size() + 1, -1);\n            bct_count_suf_dp[i].assign(bct[i].size() + 1, -1);\n            bct_mal_pre_dp[i].assign(bct[i].size() + 1, -1);\n            bct_mal_suf_dp[i].assign(bct[i].size() + 1, -1);\n            bct_count_pre_dp[i][0] = 0;\n            bct_count_suf_dp[i].back() = std::abs(bct_node_size[i]);\n            bct_mal_pre_dp[i][0] = 0;\n            bct_mal_suf_dp[i].back() = 0;\n        }\n        for (auto& mal : initial) {\n            int bct_idx = bct_rep[mal];\n            if (bct_idx < 0) continue;\n            ++bct_mal_suf_dp[bct_idx].back();\n        }\n        std::function<int(int, int)> bct_count_suf, bct_count_pre;\n        bct_count_suf = [&](int i, int j){\n            auto& dp = bct_count_suf_dp[i][j];\n            if (dp >= 0) {\n                return dp;\n            }\n            int e = bct[i][j];\n            int ej = bct_lookup[e][i];\n            return dp = bct_count_suf(i, j + 1) + bct_count_pre(e, ej) + bct_count_suf(e, ej + 1);\n        };\n        bct_count_pre = [&](int i, int j){\n            auto& dp = bct_count_pre_dp[i][j];\n            if (dp >= 0) {\n                return dp;\n            }\n            int e = bct[i][j - 1];\n            int ej = bct_lookup[e][i];\n            return dp = bct_count_pre(i, j - 1) + bct_count_pre(e, ej) + bct_count_suf(e, ej + 1);\n        };\n        std::function<int(int, int)> bct_mal_pre, bct_mal_suf;\n        bct_mal_suf = [&](int i, int j){\n            auto& dp = bct_mal_suf_dp[i][j];\n            if (dp >= 0) {\n                return dp;\n            }\n            int e = bct[i][j];\n            int ej = bct_lookup[e][i];\n            return dp = bct_mal_suf(i, j + 1) + bct_mal_pre(e, ej) + bct_mal_suf(e, ej + 1);\n        };\n        bct_mal_pre = [&](int i, int j){\n            auto& dp = bct_mal_pre_dp[i][j];\n            if (dp >= 0) {\n                return dp;\n            }\n            int e = bct[i][j - 1];\n            int ej = bct_lookup[e][i];\n            return dp = bct_mal_pre(i, j - 1) + bct_mal_pre(e, ej) + bct_mal_suf(e, ej + 1);\n        };\n        std:vector<int> bct_saved(m, 1);\n        for (int i = 0; i < m; ++i) {\n            if (bct_mal_suf(i, 0) <= 1) {\n                bct_saved[i] = bct_count_suf(i, 0);\n            } else if (bct_node_size[i] < 0) {\n                for (int j = 0; j < bct[i].size(); ++j) {\n                    if (bct_mal_suf(i, j) - bct_mal_suf(i, j + 1) == 0) {\n                        bct_saved[i] += bct_count_suf(i, j) - bct_count_suf(i, j + 1);\n                    }\n                }\n            }\n#ifdef DEBUG\n            std::cout << "saved " << i << ": " << bct_saved[i] << std::endl;\n#endif\n        }\n        std::pair<int, int> res = {0, n};\n        for (auto& mal : initial) {\n            int bct_idx = bct_rep[mal];\n            res = std::min(res, {bct_idx < 0 ? -1 : -bct_saved[bct_idx], mal});\n        }\n        return res.second;\n    }\n};\n```
[]