posts - 2,  comments - 3,  trackbacks - 0
http://acm.timus.ru/problem.aspx?space=1&num=1056

1056. Computer Net

Time Limit: 2.0 second
Memory Limit: 16 MB

Background

Computer net is created by consecutive computer plug-up to one that has already been connected to the net. Each new computer gets an ordinal number, but the protocol contains the number of its parent computer in the net. Thus, protocol consists of several numbers; the first of them is always 1, because the second computer can only be connected to the first one, the second number is 1 or 2 and so forth. The total quantity of numbers in the protocol is N − 1 (N is a total number of computers). For instance, protocol 1, 1, 2, 2 corresponds to the following net:
1 - 2 - 5
|   |
3   4
            
The distance between the computers is the quantity of mutual connections (between each other) in chain. Thus, in example mentioned above the distance between computers #4 and #5 is 2, and between #3 and #5 is 3.
Definition. Let the center of the net be the computer which has a minimal distance to the most remote computer. In the shown example computers #1 and #2 are the centers of the net.

Problem

Your task is to find all the centers using the set protocol.

Input

The first line of input contains an integer N, the quantity of computers (2 ≤ N ≤ 10000). Successive N − 1 lines contain protocol.

Output

Output should contain ordinal numbers of the determined net centers in ascending order.

Sample

input output
5
1
1
2
2
1 2
            

给定一棵树,求该树的中心。
中心定义:到其它点的距离最大值最小
树的中心即为树中最长链的中心,2次dfs即可

Code
#include<cstdio>
struct Node{

   int n;
   int next;
}EE[20001];

int ind;

int n;
int top;
int head[10001];
int check[10001];
int pre[10001];
int maxDep;
void dfs(int u, int t){
   int q;
   check[u] = 1;
   if(t > maxDep){
      maxDep = t;
      ind = u;
   }
   q = head[u];
   while(q != -1){
      if(!check[EE[q].n]){
         pre[EE[q].n] = u;
         dfs(EE[q].n, t + 1);
      }
      q = EE[q].next;
   }
}

int main(int argc, char* argv[], char* env[])

{
   int i = 0;
   int j = 0;
   while(scanf("%d", &n) != EOF){
      for(i = 1; i <= n; i++){
         head[i] = -1;
         check[i] = 0;
      }
      top = 0;
      for(i = 2; i <= n; i++){
         scanf("%d", &j);
         EE[top].n = i;
         EE[top].next = head[j];
         head[j] = top++;
         EE[top].n = j;
         EE[top].next = head[i];
         head[i] = top++;
      }
      maxDep = -1;
      dfs(1, 1);
      for(i = 1; i <= n; i++){
         check[i] = 0;
         pre[i] = -1;
      }
      maxDep = -1;
      dfs(ind, 1);
      i = ind;
      top = 0;
      while(i != -1){
         check[top++] = i;
         i = pre[i];
      }
      if(top&1){
         printf("%d\n", check[top>>1]);
      }
      else{
         printf("%d %d\n", check[(top>>1) - 1], check[top>>1]);
      }
   }
   return 0;
}
 

posted on 2011-06-20 17:30 Lshain 阅读(255) 评论(0)  编辑 收藏 引用 所属分类: Algorithm题解-timus

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿

文章分类(46)

文章档案(33)

ACM

Algorithm Link

BLOG

Format analysis

Forum

Math

mirror

OpenGL

Protocol Analyzer

Recent Contests

Search

WIN32 Programming

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜