Codeforces 687A (also named as 688C) #360 NP-Hard Problem of Vertex Cover Help Needed

codeforces 687A link

I got the problem, but couldn’t structure solution to it, so went reading tutorial,

In the tutorial code, i couldn’t get the DFS functioning. I’ll be glad if someone help me out with how are we traversing the graph.(I tried googling and reading others code buy couldn’t.)

A greedy solution will work. Store all the edges and take a mark[] array. The graph may or may not be connected. So, for each of it’s component run a DFS from any starting vertex say, X. Mark X=1. Now, in the DFS function, if the parent vertex is marked as 1, mark the children vertex with 2 else mark it with 1.
Now traverse the edge list and if any case occurs where mark==mark[v] where uv denotes an edge between u and v, then simply print -1. This is because that edge can belong to only 1 subset. So, vertex cover condition is not followed.
If no such case arise, then simply put all the 1 marked vertices in one set and 2 marked vertices in the other.
My solution

thanks rishi,