Sakshi and Art problem

#1


My code is not working for all the test cases as it’s giving wrong answers. May I know the mistake

#2

@nayakashutosh99
If i am not wrong, here your answer is just counting the number of connected components.

Here you are missing the nore written in problem statement : - “Drawing a line which is already drawn, doubles the width of line and thus it can be added to specifications, i.e. if a line is drawn again, it is treated as a distinct line in the specifications”
For understanding this, take an example of an tree like structure of graph.
For eg:- the edges are (1,2) (1,3), (1,4) here it is a connected component, but here you will have to traverse atleast one edge 2 times.

So here you will have to use the concept of euler path. If you don’t know about it, don’t worry just do google about it and have a look at this video https://www.youtube.com/watch?v=8MpoO2zA2l4&t=592s

So you just have to check for every connected component that is it a euler path or not. If not then take the count of vertices which have odd degrees. Then just figure out the number of ways to connect the total count of odd degree vertices.

#3

thank you very much!!! great explanation

1 Like