Me and my teammate maverick16 were doing the Problem I.Critical Structures, in this Problem set and this is the CF Problem page.
Our approach to this problem is :
find all the bridges and cut vertices first, remove all the bridges. now apply dfs through individual component and count the edges in that component, we divided this into two cases from here:-
- there a single cut vertex in the component remove it and count both components (components separated by cut vertex) as different
- else take the complete component as a single critical component
p will be number of components counted with this dfs + bridges q will be max edges in a component
But, this algo must fail according to us, when the graph looks like this, however it passed all tests, can anyone help with this?
Our implementation