ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1389. Roadworks

Can i use Greedy ?
Posted by Lifanov 24 Sep 2005 17:34
I take the list (any City with 1 road) and delete this road, then going to connected city and mark all road from it as non-delete, then  i going to near city and repeat first step.
For example
5 4
1 2
2 3
3 4
3 5
Start with 1 City, delete (1 2) then go in 3 city, and remove (3 4) or (3 5)?

Why WA2 ?
Sorry fo my English.
Re: Can i use Greedy ?
Posted by Pavel Tolstikov 24 Sep 2005 18:14
here is example:
8 7
1 2
2 3
3 4
3 5
4 7
7 8
5 6

Answer depends on the way you go from city 3.
Re: Can i use Greedy ?
Posted by Burunduk1 24 Sep 2005 19:45
Yes.
But your algorithm probably realy work wrong.
My greedy:
While graph is not empty
1. We choose any vertex v: deg(v)=1 (e=(v,u))
2. Add to the answer edge e.
3. Delete v and u with all its edges from the graph.
Re: Can i use Greedy ?
Posted by hoan 6 Dec 2010 22:10
why gredy is correct?
Re: Can i use Greedy ?
Posted by Mohamed K. Cena 24 Jul 2013 17:15
@Burunduk1
I used the same greedy algorithm as u did but I get WA#2, can u please help me?

Edited by author 24.07.2013 17:16