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

×

[closed] Please help find error in this code (vertex cover algorithm)

I am implementing vertex cover in tree (polynomial time algorithm) after reading the concept at geeksforgeeks . I am getting runtime error. I am storing the tree as an adjacency-list form of a graph (as tree is basically a graph).

All the implementaions I found implement the tree using structure (like we do in binary tree with left and right pointer). So they have a condition for when root is NULL.

Since the tree is represented as adjacency list, I don't think that condition is necessary (just thinking). Please tell me the reason if that part is causing the error and if so, why?

How can I fix the problem?

My code

Please help ...!!!

[EDIT] - I found an error, since the graph is undirected, when visiting the child node, there is a path back to the parent node. So this is giving an infinite loop. Use of recursion is taking stack memory causing segmentation fault. I cannot find a way around it. Making the graph directed is not working and adding a visit array like we do in DFS is giving wrong answer.

code with visit array

asked 25 Aug '16, 19:28

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

closed 25 Aug '16, 22:36

The question has been closed for the following reason "Other" by dragonemperor 25 Aug '16, 22:36


Found the error and I think I have solved it.

http://ideone.com/7jk1DT

Also another approach :

http://ideone.com/L0Pfgm

link

answered 25 Aug '16, 22:35

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

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:

×1,197
×4

question asked: 25 Aug '16, 19:28

question was seen: 554 times

last updated: 25 Aug '16, 22:36