Doritos4's blog

999E wrong ans on test case 31
By Doritos4, history, 6 years ago, In English

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:(

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

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Part two of your algorithm is not correct. You can't visit vertices in any order. For example a test case

5 4 1
3 2
3 4
4 5
5 3

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.

→ Reply