Posted on 2008-08-21 20:33
Hero 閱讀(300)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // 1056 C++ Accepted 0.031 1 045 KB
2
3 //twice BFS 第一次找離節點1最遠的點K，再找離K最遠的點X，
4 //K--X就是最長鏈，鏈上的中點就是中心 O(n)
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 const int size = 10010 ;
11 struct NODE
12 {
13 int en ;
14 struct NODE * next ;
15 NODE() { next = NULL ; }
16 };
17 struct NODE nhead[size] ;
18
19 struct QUEUE
20 {
21 int val ;
22 int level ;
23 };
24 struct QUEUE que[size] ;
25 int head, tail ;
26
27 int line[size] ;
28 int flag[size] ;
29
30 int father[size] ;
31
32 int inn ;
33
34 int fmin( int a, int b )
35 {
36 return a < b ? a : b ;
37 }
38
39 int fmax( int a, int b )
40 {
41 return a > b ? a : b ;
42 }
43
44 void input()
45 {
46 memset( father, -1, sizeof(father) ) ;
47
48 int en ;
49 for( int i=2; i<=inn; i++ )
50 {
51 scanf( "%d", &en ) ; father[i] = en ;
52 struct NODE *temp1 = (struct NODE *)malloc( sizeof(NODE) ) ;
53 temp1->en = en ;
54 temp1->next = nhead[i].next ; nhead[i].next = temp1 ;
55 struct NODE *temp2 = (struct NODE *)malloc( sizeof(NODE) ) ;
56 temp2->en = i ;
57 temp2->next = nhead[en].next ; nhead[en].next = temp2 ;
58 }//建圖
59 }
60
61 void BFS( int sn )
62 {
63 memset( flag, 0, sizeof(flag) ) ;
64 que[tail].val = sn ; que[tail++].level = 1 ; flag[sn] = 1 ;
65
66 int curn ; struct NODE *p ;
67 while( head < tail )
68 {
69 curn = que[head].val ;
70 p = nhead[curn].next ;
71 while( NULL != p )
72 {
73 if( 0 == flag[p->en] )
74 {
75 flag[p->en] = 1 ;
76 que[tail].val = p->en ;
77 que[tail++].level = que[head].level + 1 ;
78 }
79 p = p->next ;
80 }
81 head++ ;//容易忘記
82 }
83 }
84
85 void process()
86 {
87 head = tail = 0 ; BFS( 1 ) ;
88
89 int leaf = que[tail-1].val ;
90
91 head = tail = 0 ; BFS( leaf ) ;
92 }
93
94 void output()
95 {//尋找最長鏈
96
97 line[0] = 0 ; int p = tail-1 ;
98
99 int maxlen = que[tail-1].level ; line[maxlen] = que[tail-1].val ;
100 for( int i=maxlen-1; i>=1; i-- )
101 {
102 while( que[p].level > i && p>=0 ) p-- ;
103
104 while( father[que[p].val]!=line[i+1]&&father[line[i+1]]!=que[p].val && p>=0 ) p-- ;
105 line[i] = que[p].val ;
106 }
107
108 int x = (maxlen+1)/2 ;
109 if( 1 == (maxlen&1) )
110 {
111 printf( "%d\n", line[x] ) ;
112 }
113 else
114 {
115 printf( "%d %d\n", fmin( line[x], line[x+1] ), fmax( line[x], line[x+1]) ) ;
116 }
117 }
118
119 int main()
120 {
121 while( scanf( "%d", &inn ) != EOF )
122 {
123 input() ;
124
125 process() ;
126
127 output() ;
128 }
129
130 return 0 ;
131 }