Editorial for COCI '07 Contest 1 #6 Staza

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First we observe that any path ending in city $1$ ~1~ has a corresponding path starting in city $1$ ~1~. It is sufficient to reverse the sequence of roads forming the path. To simplify things, we will be trying to find the longest path starting in city $1$ ~1~.

If we observe the given network we can see that, speaking in graph theory terms, each road is either a part of a single ring, or a bridge.

In order to solve the problem, we must first identify rings and bridges. One of the ways of doing this is by constructing a DFS tree from node $1$ ~1~ and calculating all standard values (discovery time, finish time, lowlink value).

For a given ring we say that it "hangs" from node $X$ ~X~ if node $X$ ~X~ is the highest node in the DFS tree in that ring. For a given bridge we say that it "hangs" from node $X$ ~X~ if node $X$ ~X~ is the higher node in the DFS tree.

For each node $X$ ~X~ we define a subgraph of node $X$ ~X~ as the union of node $X$ ~X~ and all subgraphs of all nodes lying in rings "hanging" from $X$ ~X~ and all subgraphs of all nodes on the other side of bridges "hanging" from $X$ ~X~.

For each node $X$ ~X~ we need to find two numbers, $circle(X)$ ~circle(X)~ - path inside subgraph of node $X$ ~X~ starting and ending in $X$ ~X~, and $path(X)$ ~path(X)~ - path inside subgraph of $X$ ~X~ starting in $X$ ~X~ and ending in any node.

$circle(X)$ ~circle(X)~ can be calculated by simple recursion as sum of lengths of all rings "hanging" from $X$ ~X~ and sum of all $circle(Y)$ ~circle(Y)~ for each node $Y$ ~Y~ lying on those rings (because we can take the circle on any node $Y$ ~Y~ and end up back at $Y$ ~Y~).

When calculating $path(X)$ ~path(X)~ we need to take into account the following possible scenarios, selecting the one that yields the longest path:

The path from $X$ ~X~ ends in $X$ ~X~. This leads to $path(X) = circle(X)$ ~path(X) = circle(X)~.
We can first make a circle in subgraph of $X$ ~X~, and then take one bridge "hanging" from $X$ ~X~ into a new subgraph giving: $path(X) = circle(X) + path(Y)$ ~path(X) = circle(X) + path(Y)~ where $Y$ ~Y~ is the node on the other side of the bridge.
We can make a circle in all rings "hanging" from $X$ ~X~ except one and then select one city in that ring as the ending. In that case, there are two possible ways to arrive in the selected city so we need to find the longer way.

The solution is then $path(1)$ ~path(1)~.

Comments

There are no comments at the moment.