Discussion @ 1056. Centers of the Net @ Timus Online Judge

are there more than 2 numbers to output? ~nt~

Posted by foxX 18 Apr 2003 19:51

Re: are there more than 2 numbers to output? ~nt~

Posted by Gheorghe Stefan 28 Jul 2003 23:52

No, the idea is to make the longest road in the tree and choose the
middle nodes as the answer. It may be 1 or 2 numbers so...
That is possible in O(N) :)

Re: are there more than 2 numbers to output? ~nt~

Posted by asd 22 Jun 2005 17:10

Yes you are right... i'm trying to solve it same way. But It's a problem how to find the longest chane in the tree.

Edited by author 22.06.2005 22:48

Just BFS two times

Posted by TheBeet 10 Aug 2006 11:13

Re: Just BFS two times

Posted by Piratek-(akaDK) 30 Aug 2008 21:33

It can be solved using just one DFS. But i think ans may contain more than two numbers

Re: Just BFS two times

Posted by Seyyed Mehran Kholdi (HalfBloodCoder) 24 Oct 2008 20:52

According to Jordan's Theorem (Introduction to Graph Theory - Douglas B. West - Second Edition - Page 70), the center of a tree is a vertex or two
and you can find them this way:
Each time remove all the leaves (so the eccentricity of all the vertices will be decreased by one) and repeat this step until only one or two vertices remain

Discussion of Problem 1056. Centers of the Net