51stDimension's blog

Doubt in today's ABC 226 Problem E
By 51stDimension, history, 3 years ago, In English

Problem Link

According to the Editoral

The answer is supposed to be

Let K be = Number of components such the number of edges == number of vertices then the answer is pow(2,k)

I used the same method but I calculated the number of cycles in each connected component. Le var be a variable. And if the cyclecount in a connected component is == 1 then I do var++ and later on the ans = pow(2,var)

I am getting 6 WA.

My Code

There is a possibility that my cycleCount function is wrong. If thats the case please do let me know!

Thank you!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In circle graph your code prints 0 but it should be 2

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    4 4

    1 2

    2 3

    3 4

    1 4

    For this input my code is printing 2.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If a component does not have same number of edges and nodes answer should be 0. Did it make sense?

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The issue is that your logic has a very little flaw.

Suppose a graph has 2 connected components. One component has a cycle, while another component has 0 cycles. Answer should be 0 in that case (because there is no way to direct edges of the second component), while your logic would still say 2.

EDIT: Try this test case: 7 6 1 2 2 3 3 4 5 6 6 7 5 7

→ Reply