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[u]==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