GRAFFDEF - king Graffs Defense

can any body help me with this problem .

Thank you
link : SPOJ.com - Problem GRAFFDEF

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

1 Like

@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??

2 Likes

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

can you explain it in more detail like which particular algorithm we are using ??
thanks!!

Find all the bridges. These bridges will decompose the graph into some disconnected components. now if both soildgers are in same component then king will win. So find the probability of wining the king and then subtract from 1 for prbablity of defeating.