晓天动漫

Coding yy life……

Timus 1056. Computer net

/* 1056. Computer net 
 * File:   Timus 
 * Author: xiaotian @ hnu
 * Created on 2010年10月5日, 下午3:06
 * 题解:twice bfs 第一次找离节点1最远的点K,再找离K最远的点X,
 * K--X就是最长链,链上的中点就是中心 O(n)
 
*/

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<iostream>
#include 
<algorithm>
const int N = 10010;

struct node {
    
int en;
    node 
* next;

    node() {
        next 
= NULL;
    }
};
node nhead[N];

struct QUEUE {
    
int val;
    
int level;
};
QUEUE que[N];
int head, tail;
int line[N];
int flag[N];
int fat[N];
int n;
inline 
int min(int a,int b) { return a<b?a:b; }
inline 
int max(int a,int b) { return a>b?a:b; }
void input() {
    memset(fat, 
-1sizeof (fat));
    
int en;
    
for (int i = 2; i <= n; i++) {
        scanf(
"%d"&en);
        fat[i] 
= en;
        node 
*temp1 = (node *) malloc(sizeof (node));
        temp1
->en = en;
        temp1
->next = nhead[i].next;
        nhead[i].next 
= temp1;
        node 
*temp2 = (node *) malloc(sizeof (node));
        temp2
->en = i;
        temp2
->next = nhead[en].next;
        nhead[en].next 
= temp2;
    }
}

void bfs(int sn) {
    memset(flag, 
0sizeof (flag));
    que[tail].val 
= sn;
    que[tail
++].level = 1;
    flag[sn] 
= 1;
    
int curn;
    node 
*p;
    
while (head < tail) {
        curn 
= que[head].val;
        p 
= nhead[curn].next;
        
while (NULL != p) {
            
if (0 == flag[p->en]) {
                flag[p
->en] = 1;
                que[tail].val 
= p->en;
                que[tail
++].level = que[head].level + 1;
            }
            p 
= p->next;
        }
        head
++;
    }
}

void process() {
    head 
= tail = 0;
    bfs(
1);
    
int leaf = que[tail - 1].val;
    head 
= tail = 0;
    bfs(leaf);
}

void output() {
    line[
0= 0;
    
int p = tail - 1;
    
int maxlen = que[tail - 1].level;
    line[maxlen] 
= que[tail - 1].val;
    
for (int i = maxlen - 1; i >= 1; i--) {
        
while (que[p].level > i && p >= 0) p--;
        
while (fat[que[p].val] != line[i + 1&& fat[line[i + 1]] != que[p].val && p >= 0) p--;
        line[i] 
= que[p].val;
    }
    
int x = (maxlen + 1/ 2;
    
if (1 == (maxlen & 1))
        printf(
"%d\n", line[x]);
    
else
        printf(
"%d %d\n", min(line[x], line[x + 1]), max(line[x], line[x + 1]));

}

int main() {
    
while (scanf("%d"&n) != EOF) {
        input();
        process();
        output();
    }
    
return 0;
}

posted on 2010-10-05 16:18 晓天_xiaotian 阅读(168) 评论(0)  编辑 收藏 引用 所属分类: 图论


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


导航

<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿

随笔分类

随笔档案

相册

收藏夹

ACM Online Judge

搜索

最新评论

阅读排行榜

评论排行榜