Graph problem, TLE and RTE

Revision en1, by OmaeWaMouShenDeiru, 2015-08-08 17:02:23

Hello,

I'm trying to solve the last problem in this contest.

and this is my code, my idea is to change every strongly connected component into one node because the cost of travailing between it's nodes is ZERO, this can be done by removing all bridges and then applying union find on elements of the other edges.

Then I create new adjList using elements of the removed edges "i.e bridges", the new graph will form a tree.

Then I apply DFS two times to find the longest path in a tree.

Last step is to follow the longest path and save the sum of edges on the sides of each node, take the maximum sum between the left and right sum.

Sometimes it returns TLE and sometimes RTE.

What could be the mistake, and is there a better way to solve it.

Thanks-

Tags dfs, graphs, dsu, 100676

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English OmaeWaMouShenDeiru 2015-08-08 18:22:13 63
en1 English OmaeWaMouShenDeiru 2015-08-08 17:02:23 947 Initial revision (published)