Python3 FT 90%, O(V+E) time and space: Union-Find and Cut/Articulation Point Detection
The Idea\n\nWe can use union-find to find infected clusters.\n if a cluster has one infected node, deleting it saves the whole cluster. So the reduction is size
# The Idea\n\nWe can use union-find to find infected clusters.\n* if a cluster has one infected node, deleting it saves the whole cluster. So the reduction is size(component)\n* if a cluster has 2+ infected nodes, then we can still save some nodes if some of them are cut points (articulation points), and the new clusters created are full of only uninfected nodes\n\nUnion-find and finding cut/articulation points both run in O(V+E) time.\n\nSee the code for details and more explanation.\n\nIn a way this solution is more complicated than the union-find-merge-clusters solutions because you need to find articulation points. And that\'s a relatively advanced algorithm.\n\nBut on the other hand, that algorithm (`findCuts`) isn\'t too hard to code up once you know it.* And you benefit from a simpler explanation - the code very directly answers the question "if I deleted this infected node, would I create a new cluster(s) of uninfected nodes?"\n\n*be VERY careful of replacing `v` with `p`, etc. though!\n\n# Code\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        debug = False\n\n        # if we delete node u:\n        #   if u is not a cut point: reduction is componentSize if u is the only infected node, else 0\n        #   if u is a cut point: removing u isolates 1 or more child components from the rest of the graph\n        #       if the component that would be isolated has zero infected nodes, removing u saves all nodes\n        #          from infection. So we\'ll add those nodes to a running total for u\n        #       otherwise there is 1+ infected node, so eventually the whole component will become infected.\n        #          So no nodes in that component will be saved.\n\n        # Finding cut points is a known DFS algo, onto which we can bolt on summing up clean and total node counts easily\n\n        # So the steps are\n        #   1. identify the connected components with union find\n        #   2. for each connected component with an infected vertex: what infected vertices are in there\n        #   3. scan over those infected components\n        #       a. if there\'s only one infected node, deleting it saves the whole cluster\n        #       b. if there are 2+, find cut points in the component. Then if an infected\n        #          vertex u is a cut point, then number of nodes saved is\n        #             i. clean nodes in "sub-components" that become isolated if we delete u\n        #             ii. plus 1 for the infected vertex we delete\n\n        N = len(graph)\n\n        ### (1) UNION-FIND\n        p = [-1]*N # -size if root, else parent\n\n        def getRoot(u: int) -> int:\n            if p[u] < 0:\n                return u\n\n            p[u] = getRoot(p[u])\n            return p[u]\n\n        def union(u: int, v: int) -> None:\n            ru = getRoot(u)\n            rv = getRoot(v)\n\n            if ru == rv:\n                return\n\n            # union smaller component into larger component\n            if p[rv] < p[ru]:\n                ru, rv = rv, ru\n\n            p[ru] += p[rv]\n            p[rv] = ru\n\n        adj = defaultdict(list)\n        for u in range(N):\n            for v in range(u):\n                if graph[u][v]:\n                    union(u, v)\n                    adj[u].append(v)\n                    adj[v].append(u)\n\n        if debug: \n            for i in range(N): \n                js = list(j for j in adj[i])\n                print(f"adj {i}: {js}")\n\n        ### (2) FIND INFECTED COMPONENTS AND THEIR INFECTED VERTICES\n        ccs = defaultdict(list) # infected CC root -> infected vertices\n        for u in initial:\n            ccs[getRoot(u)].append(u)\n\n        ### (3) PROCESS EACH INFECTED COMPONENT\n        time = [-1]*N\n        lo = [-1]*N\n        reductions = defaultdict(int) # infected index => the total reduction we get\n        infset = set(initial)\n\n        def findCuts(u: int, p: int, t: int, sz: int, ninf: int) -> tuple[int, int]:\n            """\n            Detects if u is a cut point. If so, and it isolates\n            a cluster of all uninfected nodes from a cluster of infected nodes,\n            then it increments reductions by that that number.\n\n            Returns the number of clean and total nodes reachable from u without visiting p.\n\n            Updates time and lo.\n            """\n\n            # This is a variation on identifying cut points, see https://cp-algorithms.com/graph/cutpoints.html,\n            # modified to return node counts; the "plain vanilla" algo just identifies vertices that are\n            # cut points.\n\n            time[u] = t\n            lo[u] = t\n            total = 1\n            clean = 0 if u in infset else 1\n            for v in adj[u]:\n                if v == p: continue\n                \n                if time[v] == -1:\n                    if debug: print(f"  time[{u}] = {time[u]}, visiting {v} with time {t+1}")\n                    cl, ttl = findCuts(v, u, t+1, sz, ninf)\n                    if lo[v] >= time[u]:\n                        # deleting v isolates u and all reachable except via u-v\n                        if cl == ttl:\n                            reductions[u] += cl\n                    \n                    clean += cl\n                    total += ttl\n\n                # regardless\n                if lo[v] < lo[u]:\n                    if debug: print(f"  {u}: non-parent(=={p}) neighbor {v} has lo[{v}] {lo[v]} < lo[{u}] {lo[u]}. Updating lo[{u}]")\n                    lo[u] = lo[v]\n\n            # NOTE: we don\'t need this (and thus sz and numInf as params either) by always picking\n            #       an infected node as the root. this way the "ancestor cluster" and yet-unvisited\n            #       nodes will contain at least one infected node so we know that isolating them\n            #       won\'t reduce the solution (well yet-unvisited nodes might, but they\'ll be picked\n            #       up when visited later on)\n            # (this was a bug I had to fix!!)\n            # if lo[u] == time[u]:\n            #     # DFS from u never touched p and other ancestor nodes,\n            #     # so we include the "ancestor cluster" will all other nodes\n            #     cl = (sz - ninf) - clean\n            #     ttl = sz - total\n            #     if cl == ttl:\n            #         reductions[u] += cl\n\n            if debug: print(f"node {u}: time[u] = {time[u]}, lo[u] = {lo[u]}, clean={clean}, total={total}, sz={sz}, numInf={numInf}")\n\n            return clean, total\n\n        bestReduction = 0\n        bestVertex = min(initial)\n        for r, inf in ccs.items():\n            sz = -p[r]\n            numInf = len(inf)\n            if numInf == 1:\n                u = inf[0]\n                \n                if sz > bestReduction or (sz == bestReduction and u < bestVertex):\n                    bestReduction = sz\n                    bestVertex = u\n\n                if debug: print(f"iso: deleting {u} would reduce inf by {sz}")\n\n            else:\n                maxReductionPossible = sz - numInf + 1 # isolate all size(CC)-len(inf), plus 1 for deleting an infected node\n                if maxReductionPossible < bestReduction: continue\n                if maxReductionPossible == bestReduction and all(u > bestVertex for u in inf): continue # same reduction, but worse index\n\n                # BUG FIX: start from an infected node\n                # that way we don\'t have to handle the edge case where a cut point isolates all len(inf) infected\n                # nodes from the "ancestor cluster" with only clean nodes\n                if debug: print(f"finding cut points starting from {inf[0]}")\n                findCuts(inf[0], -1, 0, sz, numInf)\n                for u in inf:\n                    if reductions[u] + 1 > bestReduction or (reductions[u] + 1 == bestReduction and u < bestVertex):\n                        # +1 because we isolate all the clean nodes, and also delete an infected node\n                        bestReduction = reductions[u] + 1\n                        bestVertex = u\n\n                    if debug: print(f"cut: deleting {u} would reduce inf by {reductions[u] + 1}")\n\n        return bestVertex\n```
['Python3']