×

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

 0 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.) asked 06 Nov '17, 16:26 87●5 accept rate: 0%

 0 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 answered 06 Nov '17, 17:03 5★rishi_07 316●1●7 accept rate: 20% thanks rishi, (07 Nov '17, 08:00)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×726
×682

question asked: 06 Nov '17, 16:26

question was seen: 302 times

last updated: 06 Nov '17, 17:04