学步园

1056. Computer net

/*<br /> * File: Timus<br /> * Author: xiaotian @ hnu<br /> * Created on 2010年10月5日, 下午3:06<br /> * 题解：twice bfs 第一次找离节点1最远的点K，再找离K最远的点X，<br /> * K--X就是最长链，链上的中点就是中心 O(n)<br /> */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <string.h><br /> #include <iostream><br /> #include <algorithm><br /> const int N = 10010;<br /> struct node {<br /> int en;<br /> node * next;<br /> node() {<br /> next = NULL;<br /> }<br /> };<br /> node nhead[N];<br /> struct QUEUE {<br /> int val;<br /> int level;<br /> };<br /> QUEUE que[N];<br /> int head, tail;<br /> int line[N];<br /> int flag[N];<br /> int fat[N];<br /> int n;<br /> inline int min(int a,int b) { return a<b?a:b; }<br /> inline int max(int a,int b) { return a>b?a:b; }<br /> void input() {<br /> memset(fat, -1, sizeof (fat));<br /> int en;<br /> for (int i = 2; i <= n; i++) {<br /> scanf("%d", &en);<br /> fat[i] = en;<br /> node *temp1 = (node *) malloc(sizeof (node));<br /> temp1->en = en;<br /> temp1->next = nhead[i].next;<br /> nhead[i].next = temp1;<br /> node *temp2 = (node *) malloc(sizeof (node));<br /> temp2->en = i;<br /> temp2->next = nhead[en].next;<br /> nhead[en].next = temp2;<br /> }<br /> }<br /> void bfs(int sn) {<br /> memset(flag, 0, sizeof (flag));<br /> que[tail].val = sn;<br /> que[tail++].level = 1;<br /> flag[sn] = 1;<br /> int curn;<br /> node *p;<br /> while (head < tail) {<br /> curn = que[head].val;<br /> p = nhead[curn].next;<br /> while (NULL != p) {<br /> if (0 == flag[p->en]) {<br /> flag[p->en] = 1;<br /> que[tail].val = p->en;<br /> que[tail++].level = que[head].level + 1;<br /> }<br /> p = p->next;<br /> }<br /> head++;<br /> }<br /> }<br /> void process() {<br /> head = tail = 0;<br /> bfs(1);<br /> int leaf = que[tail - 1].val;<br /> head = tail = 0;<br /> bfs(leaf);<br /> }<br /> void output() {<br /> line[0] = 0;<br /> int p = tail - 1;<br /> int maxlen = que[tail - 1].level;<br /> line[maxlen] = que[tail - 1].val;<br /> for (int i = maxlen - 1; i >= 1; i--) {<br /> while (que[p].level > i && p >= 0) p--;<br /> while (fat[que[p].val] != line[i + 1] && fat[line[i + 1]] != que[p].val && p >= 0) p--;<br /> line[i] = que[p].val;<br /> }<br /> int x = (maxlen + 1) / 2;<br /> if (1 == (maxlen & 1))<br /> printf("%d/n", line[x]);<br /> else<br /> printf("%d %d/n", min(line[x], line[x + 1]), max(line[x], line[x + 1]));<br /> }<br /> int main() {<br /> while (scanf("%d", &n) != EOF) {<br /> input();<br /> process();<br /> output();<br /> }<br /> return 0;<br /> }