Can anyone tell me which test case fails in this code?

Problem

My Solution

Thanks

what if m is already even?

if M is even and there is only one cycle it print 1 N times

1

6 5

2 3

3 4

4 5

5 6

6 2

for this your program is giving

3

1 1 2 3 3 3

3rd group has 3 edges

No Bro, 4 is connected to 5 and 5 is connected to 6 there are only two edges

If M is even as pointed out by others. And secondly, consider the graph with 10 nodes,7 edges and 3 connected components. First with 3 edges and 3 nodes 1,2,3(Means form a cycle). Second similar to the first 3 nodes and 3 edges 4,5,6. And third an edge between 7 and 8. Clearly the answer should be 2 but your code gives 3. Keep track of minimum and it will pass.

my bad(20 char limitâ€¦)

I think your mean is thisâ€¦

10 7

1 2

2 3

3 1

4 5

5 6

6 4

7 8

my output is

3

1 2 3 1 2 3 2 1 1 1

I think itâ€™s correct

No. it will be

1 1 1 1 1 1 1 2

you should minimize the answer

1 Like

Thereâ€™s no need to do DFS, the problem is pretty simple.

Letâ€™s suppose that the number of edges are even, then the answer is simply 1.

The question gets interesting when the number of edges are Odd.

For that there are two subcases:

- The degree of all vertices is even(E.g A pentagon with 5 edges, edges b/w 1 2 , 1 3 , 2 4, 3 5,4 5)
- The degree of at least one vertex is odd

In first case what you need to do is, take any vertex whose degree is greater than 1 and even. Letâ€™s call this as vertex A, and take one of itâ€™s adjacent vertex. Letâ€™s call this as vertex B. From the original Graph, delete vertex A and B. And put A and B into different subgraph, so that way youâ€™ll get K=3 with All vertex other than A and B belonging to 1 Subgraph and A belong to 2 (or 3) and B belong to 3(or 2)

in second case, you just need to remove the odd degree vertex and put it into different subgraph and yourâ€™e done. K=2 with all vertices other than the odd degree one belonging to 1st and odd one belongs to 2nd subgraph.

Hope that it helps, try to code this logic, if you run into some error, let me know. Iâ€™ll be happy to help.

7 Likes

Answer is wrong, Value of K is 2 for the given input.

1 Like

Thanks Broâ€¦ for your effortsâ€¦

I hope you got it. Keep track of minimum .

In line no 90, for the case where a graph has odd no of edges but still all the vertices have even degree of edges, you are taking something like this g[v][0]. Instead of doing this, you should have

done something like this

If (Length(g[v])+ length (g[v][any child of v])-1)%2==1

Then make that child to be in 3

This would have ensured that 2 vertices that you are removing have odd no of edges when removed together.

Donâ€™t you think this will always be the case?

Odd Edge Graph containing all even edges, removing 2 nodes (1 common edge) => even edges + even edges - 1 (common edge)

Try changing the code and test

Arey bhai.

Try to loop over vertex Vâ€™s children. Once you hit the condition break it.

Do this and report

Brother the question is very simple you

Prerequisites:- Adjacency list representation of graphs.

A graph can have any number of edges. There are just 3 cases here.

Case:- 1 A graph has even edges just include all vertices in one group.

CASE:2 A graph has odd edges and at least one vertex have odd number of edges attached to it. In this case you need to just keep this vertex out in a separate group and all other nodes together in a group

Case:3:- A graph has odd number of edges and all vertices have even edges attached to it. Then what we can do is that break any vertex from the graph that have even edges greater than 0 attached to it and then the remaining subgraph will have odd edges and there will be one node having odd edges connected to it now simply break this node , you can do it more simply by just breaking any one vertex that had even number of edges attached to it and put another node which was earlier connected to that node which we have broken just now so we already had 2 groups and other remaining nodes will be in 3 groups , you can view my easy submission too for that problem

2 Likes