PROBLEM LINK:
Author: Manish Pathak
Tester: Manish Pathak
Editorialist: Manish Pathak
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory,DFS,Bridges
PROBLEM:
There is a Dictator in Chefland who wants to capture various islands.
He is a very clever person,first he makes a very good plan then he attack the island with his army and capture it.There are N islands in the chefland numbered from 1,2,…N and there is a bidirectional connectivity between some of them.
Plan for attacking the island is:-
They will attack only those island on which after removal of the connections(between any two islands) the graph will have more than one connected components.
EXPLANATION:
Here in the plan for attacking the island suggest that we must remove those edges from undirected graph which will give more than one connected components which clearly means we have to find the bridges in the given graph.
Algorithm:
We will run DFS from an arbitrary vertex say v then the current edge (v,u) is a bridge if there is no way from v to u except (v,u).For this purpose we will use time of entry into a node computed by DFS.
For more clarification see the implementation.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here