GRAFFDEF - king Graffs Defense

can any body help me with this problem .

Thank you
link : http://www.spoj.com/problems/GRAFFDEF/

tips:Using a biconnected component shrink point for the graph, the problem on the new graph is simple.

@freeloop Can this problem be solved by Bridge tree where the edges which on deletion do not disconnect the graph are compressed into a single node and the edges which are bridges are used to connect these nodes??

1 Like

You are right, The graph will be compressed into a tree where each edge is a bridge in the original graph.

https://cp-algorithms.com/graph/bridge-searching.html