I'm getting wa31 for this problem ( my submission ).
First, I find all vertices that can be reached from the capital. Then, I look at all vertices which have indegree equal to 0. These vertices must have an edge directly connecting them to the capital and can obviously be visited in any order. Now, if unvisited vertices remain, they must form a cycle. I visit these vertices next ( again, in any order).
Please help
Edit : I'm getting wa32 now:(
Part two of your algorithm is not correct. You can't visit vertices in any order. For example a test case
If you visit vertices in order 2 3 4 5 you will get two additional edges (1->2 and 1->3). But if you visit vertices in order 3 4 5 2 you will get only one addition edge (1->3), and the answer for the test case is 1.