problem with a tree that for you should be easy

IBelieve · Post by **IBelieve** » Sat Dec 06, 2003 6:45 pm

Hi ..
This is killing me:
You are given a tree with N vertexes. Write a program, that adds (if possible) a minimum number of edges so that each vertex becomes a part of not more than ONE cycle.
Sample input:
n=7
1 2
1 3
3 5
3 4
5 6
5 7
sample output:
6 7
4 2

can you give me at least some basic hints. i need to do this one till monday otherwise i'm dead.

[/i]

Cosmin.ro · Post by **Cosmin.ro** » Sun Dec 07, 2003 5:11 am

You have to work with the biconnected components algo. But if you are from Cluj you should have acces to Ginfo where this is solved. Send me a private message if you really need to solve this.

IBelieve · Post by **IBelieve** » Sun Dec 07, 2003 8:31 pm

Cosmin.ro wrote:You have to work with the biconnected components algo. But if you are from Cluj you should have acces to Ginfo where this is solved. Send me a private message if you really need to solve this.

lots of thanks