OmaeWaMouShenDeiru's blog

Graph problem, TLE and RTE
By OmaeWaMouShenDeiru, history, 9 years ago, In English

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.

EDIT: now this code gets WA

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

You should use Tarjan's Algorithm to find all the strongly connected components instead. Compress every strongly connected component into a single node and the graph will become a tree. Then just dfs finding the longest distance of each node and choose the lowest one.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by OmaeWaMouShenDeiru (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved this problem using Tarjan's Algorithm .

you can modify it for this problem , see my code my code .

then I find longest path in tree just like you do .

OmaeWaMouShenDeiru

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm still looking for the reason behind WA verdict in my code, do you have any idea why ??

    → Reply