Обсуждение @ 1056. Центры сети @ Timus Online Judge

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

Послано foxX 18 апр 2003 19:51

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

Послано Gheorghe Stefan 28 июл 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~

Послано asd 22 июн 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

Послано TheBeet 10 авг 2006 11:13

Re: Just BFS two times

Послано Piratek-(akaDK) 30 авг 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

Послано Seyyed Mehran Kholdi (HalfBloodCoder) 24 окт 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

Обсуждение задачи 1056. Центры сети