You are not logged in. Please login at www.codechef.com to post your questions!

×

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.)

asked 06 Nov '17, 16:26

ashigahlawat's gravatar image

2★ashigahlawat
875
accept rate: 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

link

answered 06 Nov '17, 17:03

rishi_07's gravatar image

5★rishi_07
31617
accept rate: 20%

edited 06 Nov '17, 17:04

thanks rishi,

(07 Nov '17, 08:00) ashigahlawat2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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