If you haven't yet taken a look at my hint, please do so:

http://codersblock.net/ccc/2007/construction/hint.txt


-----------
So how do we find the number of strongly connected components?
-----------
To be honest, I am not exactly sure. I have come up with my own algorithm that finds it in linear time, by finding the highest cycle for each node.

Whether or not this is the standard method, I am not sure. Haven't learned this stuff yet... But it surely is efficient, because
it only checks each edge and vertex once. This is optimal, considering we need to at least acknowledge every edge and vertex.


-----------
See the following graphical depiction of my algorithm for finding strongly connected nodes:
-----------
http://codersblock.net/ccc/2007/construction/dfs.png


----------
Figure 1.1
----------
A graph in standard form.
 
----------
Figure 1.2
----------
We run a depth first search, pre-ordering each node. In this case, edges are chosen first alphabetically, but ordering does not matter.

----------
Figure 1.3
----------
While everything's being preordered, an important step is being made, the highest cycle is being kept track of for -every- node, starting from the bottom, working its way up to the top.
 
The highest cycle works with the "min" function, which constantly merges the pre-order value of each backedge, with the pre-order value of each child's backedge. The highest cycle is the smallest pre. 
The importantance of the highest cycle is it indicates all edges that can't be removed, because a secondary path exists for all nodes between that node and its highest cycle.
 
If there are no cycles for the current node, an arbitrary constant value of NIL, -1, is kept.
 
For example, D is the first node to start merging. It has determined its highest cycle to be its only backedge, A. 
It returns that value to its parent, E. E determines A to be its highest cycle as well.

All cycles are merged, starting from the bottom to the top, until a pre-order is found that's equal or greater than the preorder of the current node. 
The crucial property of this is: nothing cycles above the current node. More specifically, there's only one path to the current node from A. 
The connection between itself and its parent is the only path, therefore its edge separates the nodes below into a strongly connected component. 

A table is given in chronological order, to show the highest cycle of each node, and whether or not that indicates a strongly connected component.

-----------
Now, back to the question:
-----------

We find all strongly connected components, and each time we discover one, we increment answers++, AND we add a bandaid road to the top. 
The band-aid road is accomplished by returning the pre-order "0" as the highest cycle.
This essentially notifies the parent that there's a new road to the top, without even adding one to the graph.

The final output is (answers+1)/2.
This is because every two strongly connected components can be fixed by a road that joins the two of them. That is the best case, and can always be done. 

Why? 
Because adding a road between two strongly connected components makes each no longer connected by only one critical road.
If there are an odd number of strongly connected components, you only need one more road that connects it to the top. Hence the (...+1)/2.