Table of content
Save Us ARTPNT
Original Problem Link: ARTPNT
Author Name: Mohammed Shahraaz Hussain linkedin link
Prequisutes: Block Cut Tree and Dp on Trees.
Explaination:
First, let us solve this for a tree. For the root, we check how
many children subtrees are totally infection free and how many
have at least one infected. If no child subtree has at least one
infected we save the whole tree except the infected person.
Otherwise, we save all subtree which is infection-free. By
rerooting, we can solve this for the whole tree. And choose the
best node.
Now for a general graph, we can find the block cut tree (idea from
here
https://www.quora.com/q/threadsiiithyderabad/The-Bridge-Tree-of-a-graph
Code from https://ideone.com/hCUME3 I edited it a bit).
Some picture of to give u an idea of what must be done
Original Graph
Block Cut Tree
Observation removing articulation points is the best. Each node in
the block cut tree is a combination of multiple nodes in the input
graph. We need to check if a node of the block cut tree represents
only one node in the input graph, also check if that node is an
articulation point in the original graph and finally check if the
node is infected. If all the checks pass do some similar
computation for the node and consider that node
