Can anyone tell me which test case fails in this code?
Problem
My Solution
Thanks
1 Like
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