What am I missing?

#1

I’m trying to make this thing into a Euler path because that’s what the question is essentially about

my approach:

1)assign degrees to each vertex

2)find the number of even components(components with no odd degree vertex)

3)find the number of odd components(components with at least 1 odd degree vertex)

4)find the number of odd degree vertices in each component

5)connect all the even components

6)connect all the odd components

7)connect the final two components.

Am I missing something here?

I’ve considered the cases where even components =0 or when the odd components = 0 and they’re working.
I’ve also figured out that these are, in fact, the only test cases that got accepted.

I got only 2/6 test cases correct.
Is it because of long long int??

#2

halp ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

#3

Hey @aayushmathur05
Sorry for the delay. Here you go. Some changes in your logic.

  1. Count the number of vertices(count of the open ends) with odd degree in a component. If there is no vertex with odd degree, in a connected component, consider that there are two open ends, so add two to the count.

  2. You can leave at most two open ends unpaired. That means, the number of pairings that need to be done are the minimum number of edges to be added.

#4

can you elaborate a bit here? why did you add two instead of one

#6

This condition is for Euler Circuit.
A Euler Path has exactly two vertices with odd degree.

#8

Yes, we do need an entrance edge and an exit edge but consider this:
We start from an edge that already exists inside the even component, but since we need an exit, we add 1edge to this even connected component.
In this case, we didn’t have to add 2 edges because we started from an edge that already existed inside the even connected component.

#9

Asking someone else to join in and help you out. Thanks for your patience.

#10

alright
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

#11

Can you send me the question link

#12

Hi,
Two is added in the count of vertices. Finally we have to give the number of pairings so two vertices give one edge ultimately.

Hope it helps.

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#14

could you tell me the test case that i get wrong?