I was trying to solve problem H in this gym contest , the problem shortly states:
given a connected graph you are required to add one edge so that the number of bridges in the graph is minimized, an edge is called bridge if and only if removing it makes the graph disconnected.
the solution is very simple , find bridges in O(n+m) then change every connected component of non-bridge edges into one node , then you will have a tree consisting of bridge edges only , then find the length of diameter of tree and subtract it from the number of bridges and this is the final answer
this algorithm is O(n+m) time and memory but when I coded it , it gave me Memory limit exceeded which is very strange since all arrays which I allocated can't be more than 256MB , here's my code which took MLE.
then I tried to code it without using structs or pointers but I used vectors, and it got AC with only 16MB memory , link to my AC code , as you can see there's big difference in memory and I have no idea what is happening.
I wrote a code that calculate the sum of number of nodes and the number of edges in all test cases of input file and the result was: sum of nodes=639884 , sum of edges=678426
any help explaining the MLE would be appreciated.