haleyk100198's blog

By haleyk100198, history, 8 years ago, In English

Link to problem: http://mirror.codeforces.com/problemset/problem/505/D

My submission: http://mirror.codeforces.com/contest/505/submission/18861557

My idea is to count the amount of sub-trees of the graph that doesn't contain a cycle, and the answer would be n-(amount of sub-trees without a cycle). However my code fails on the test case 6 and I have no idea how did the test case got me... Can anyone point out the flaw of my code or even my approach on solving this problem?

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

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Here is test 16 that fails your program. Also, graph can't be called a tree if it has cycle.

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

    Thanks for the test case, now I see the flaw my logic, didn't thought through the whole merge algorithm. :D

    Also for pointing out the wrong tag, now it has been updated.