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

foxX are there more than 2 numbers to output? ~nt~ [5] // Problem 1056. Centers of the Net 18 Apr 2003 19:51

Gheorghe Stefan Re: are there more than 2 numbers to output? ~nt~ [4] // Problem 1056. Centers of the Net 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) :)

asd Re: are there more than 2 numbers to output? ~nt~ [3] // Problem 1056. Centers of the Net 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

TheBeet Just BFS two times [2] // Problem 1056. Centers of the Net 10 Aug 2006 11:13

Piratek-(akaDK) Re: Just BFS two times [1] // Problem 1056. Centers of the Net 30 Aug 2008 21:33

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

Seyyed Mehran Kholdi (HalfBloodCoder) Re: Just BFS two times // Problem 1056. Centers of the Net 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