#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX 5000 /* */
typedef struct node Node;
struct node {
int id;
int depth;
int which;
Node* next;
}; /* ---------- end of struct Node ---------- */
#define True 1 /* */
#define False 0 /* */
#define heightes 0 /* */
#define secondary 1 /* */
short int visited[MAX+1];
int maxHeight[MAX+1];
/*
* === FUNCTION ======================================================================
* Name: dfsForLeaf
* Description:
* =====================================================================================
*/
void
dfsForLeaf ( Node tree[], int w, int n, int depth )
{
int i = 1;
Node *pointer = NULL;
visited[w] = True;
maxHeight[w] = depth;
for ( pointer = tree[w].next ; NULL != pointer ; pointer=pointer->next ) {
if ( !visited[ pointer->id ] ) {
dfsForLeaf(tree, pointer->id, n, depth+1);
}
}
return ;
} /* ----- end of function dfsForLeaf ----- */
/*
* === FUNCTION ======================================================================
* Name: findBestRoot
* Description:
* =====================================================================================
*/
void
findBestRoot ( Node tree[], int knownLeaf, int n )
{
int i = 1, j =0;
int currentLeaf, bestNodeTop=0, worstNodeTop = 0;
int maxLen = -1;
int worstNode[MAX], bestNode[MAX];
/* initial */
memset(visited
, False
, sizeof(short int)*MAX
); memset(maxHeight
, 0, sizeof(int)*MAX
); DFS(tree, knownLeaf, n); /* for leaf node */
currentLeaf = tree[knownLeaf].which; /* the end node of longest path */
maxLen = -1;
memset(visited
, False
, sizeof(short int)*MAX
); memset(maxHeight
, 0, sizeof(int)*MAX
); DFS(tree, currentLeaf, n);
for ( i=1; i<=n; i++ ) {
if ( maxLen < maxHeight[i] ) {
maxLen = maxHeight[i];
currentLeaf = i;
}
}
if ( 0 == maxLen % 2 ) { /* only one root node */
for ( i=1; i<=n ; i++ ) {
if ( maxLen/2 == maxHeight[i] ){
bestNode[bestNodeTop] = i;
bestNodeTop += 1;
}
}
memset(visited
, False
, sizeof(short int)*MAX
); memset(maxHeight
, 0, sizeof(int)*MAX
); dfsForLeaf(tree, bestNode[0], n, 0);
for ( i=1; i<=n ; i++ ) {
if ( maxLen/2 == maxHeight[i] ){
worstNode[worstNodeTop] = i;
worstNodeTop += 1;
}
}
}
else { /* two best nodes */
for ( i=1; i<=n ; i++ ) {
if ( maxLen/2 == maxHeight[i] || (maxLen/2)+1 == maxHeight[i] ) {
bestNode[bestNodeTop] = i;
bestNodeTop += 1;
}
}
for ( i=bestNodeTop-1; i>=0 ; i-- ) { /* get the worst nodes */
memset(visited
, False
, sizeof(short int)*MAX
); memset(maxHeight
, 0, sizeof(int)*MAX
); dfsForLeaf(tree, bestNode[i], n, 0);
for ( j=1; j<=n ; j++ ) {
if ( 1+(maxLen/2) == maxHeight[j] ){
worstNode[worstNodeTop] = j;
worstNodeTop += 1;
}
}
}
}
for ( i=0; i<bestNodeTop ; i++ ) {
printf ( " %d", bestNode
[i
] ); }
for ( i=0; i<worstNodeTop ; i++ ) {
printf ( " %d", worstNode
[i
] ); }
return ;
} /* ----- end of function findBestRoot ----- */
/*
* === FUNCTION ======================================================================
* Name: DFS
* Description:
* =====================================================================================
*/
int
DFS ( Node tree[], int w, int n )
{
int i = 1, max=-1;
Node *pointer = NULL;
visited[w] = True;
for ( pointer = tree[w].next ; NULL != pointer ; pointer=pointer->next ) {
if ( !visited[ pointer->id ] ) {
i = DFS(tree, pointer->id, n);
if ( max < i ) { /* the endpoint of longer path */
max = i;
tree[w].which = tree[pointer->id].which;
}
}
}
maxHeight[w] += ( max+1 );
if ( 0 == maxHeight[w] )
tree[w].which = w;
return maxHeight[w];
} /* ----- end of function DFS ----- */
/*
* === FUNCTION ======================================================================
* Name: main
* Description:
* =====================================================================================
*/
int
main ( int argc, char *argv[] )
{
int i = 0, j = 0; /* counter */
int n = 0, t = 0, k = 0; /* temp variable */
int rootId = 0;
int knownleaf = 0;
Node nodeList[MAX+1];
Node *temp = NULL, *head=NULL, *tail=NULL; /* temp variable */
while ( EOF
!= scanf("%d", &n
) ) { /* total nodes */
for ( i = 1; i <= n ; i++ ) {
head = temp = NULL;
nodeList[i].depth = 0;
scanf ( "%d", &t
); /* neighbor amounts */ for ( j=0; j < t ; j++ ) {
if ( NULL == head ) {
head
= (Node
*)malloc(sizeof(Node
)); head->id = k;
head->depth = 0;
head->which = -1;
tail = head;
}
else {
temp
= (Node
*)malloc(sizeof(Node
)); temp->id = k;
temp->next = NULL;
temp->depth = 0;
head->which = -1;
tail->next = temp;
tail = temp;
}
nodeList[i].depth += 1;
}
nodeList[i].next = head;
}
/* initial */
memset(visited
, False
, sizeof(short int)*MAX
); for ( i=1; i<=n ; i++ )
maxHeight[i] = 0;
for ( i=1; i<=n ;i++ ) { /* find a leaf node and go DFS from him */
if ( 1 == nodeList[i].depth ) {
knownleaf = i;
break;
}
}
findBestRoot( nodeList, knownleaf, n);
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8bWF0aC5oPgoKI2RlZmluZQlNQVggNTAwMAkJCS8qICAqLwoKdHlwZWRlZiBzdHJ1Y3Qgbm9kZSBOb2RlOwpzdHJ1Y3Qgbm9kZSB7CgkJaW50IGlkOwoJCWludCBkZXB0aDsKCQlpbnQgd2hpY2g7CgkJTm9kZSogbmV4dDsKfTsJCQkJLyogLS0tLS0tLS0tLSAgZW5kIG9mIHN0cnVjdCBOb2RlICAtLS0tLS0tLS0tICovCgoKI2RlZmluZQlUcnVlIDEJCQkvKiAgKi8KI2RlZmluZQlGYWxzZSAwCQkJLyogICovCgojZGVmaW5lCWhlaWdodGVzIDAJCQkvKiAgKi8KI2RlZmluZQlzZWNvbmRhcnkgMQkJCS8qICAqLwoKc2hvcnQgaW50IHZpc2l0ZWRbTUFYKzFdOwppbnQgbWF4SGVpZ2h0W01BWCsxXTsKCgovKiAKICogPT09ICBGVU5DVElPTiAgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQogKiAgICAgICAgIE5hbWU6ICBkZnNGb3JMZWFmCiAqICBEZXNjcmlwdGlvbjogIAogKiA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CiAqLwoJCXZvaWQKZGZzRm9yTGVhZiAoIE5vZGUgdHJlZVtdLCBpbnQgdywgaW50IG4sIGludCBkZXB0aCApCnsKCQlpbnQgaSA9IDE7CgkJTm9kZSAqcG9pbnRlciA9IE5VTEw7CgkJdmlzaXRlZFt3XSA9IFRydWU7CgkgCW1heEhlaWdodFt3XSA9IGRlcHRoOwoJCWZvciAoIHBvaW50ZXIgPSB0cmVlW3ddLm5leHQgOyBOVUxMICE9IHBvaW50ZXIgOyBwb2ludGVyPXBvaW50ZXItPm5leHQgKSB7CgkJCQlpZiAoICF2aXNpdGVkWyBwb2ludGVyLT5pZCBdICkgewoJCQkJCSBkZnNGb3JMZWFmKHRyZWUsIHBvaW50ZXItPmlkLCBuLCBkZXB0aCsxKTsKCQkJCX0KCQl9CgkJCgkJcmV0dXJuIDsKfQkJLyogLS0tLS0gIGVuZCBvZiBmdW5jdGlvbiBkZnNGb3JMZWFmICAtLS0tLSAqLwoKLyogCiAqID09PSAgRlVOQ1RJT04gID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KICogICAgICAgICBOYW1lOiAgZmluZEJlc3RSb290CiAqICBEZXNjcmlwdGlvbjogIAogKiA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CiAqLwoJCXZvaWQKZmluZEJlc3RSb290ICggTm9kZSB0cmVlW10sIGludCBrbm93bkxlYWYsIGludCBuICkKewoJCWludCBpID0gMSwgaiA9MDsKCQlpbnQgY3VycmVudExlYWYsIGJlc3ROb2RlVG9wPTAsIHdvcnN0Tm9kZVRvcCA9IDA7CgkJaW50IG1heExlbiA9IC0xOwoJCWludCB3b3JzdE5vZGVbTUFYXSwgYmVzdE5vZGVbTUFYXTsKCgkJCQkJCQkJCQkvKiBpbml0aWFsICovCgkJbWVtc2V0KHZpc2l0ZWQsIEZhbHNlLCBzaXplb2Yoc2hvcnQgaW50KSpNQVgpOwoJCW1lbXNldChtYXhIZWlnaHQsIDAsIHNpemVvZihpbnQpKk1BWCk7CgkJREZTKHRyZWUsIGtub3duTGVhZiwgbik7ICAgICAgICAgICAgICAgIC8qIGZvciBsZWFmIG5vZGUgKi8KCQkKCgkJY3VycmVudExlYWYgPSB0cmVlW2tub3duTGVhZl0ud2hpY2g7ICAgIC8qIHRoZSBlbmQgbm9kZSBvZiBsb25nZXN0IHBhdGggICovCgkJbWF4TGVuID0gLTE7CgkJbWVtc2V0KHZpc2l0ZWQsIEZhbHNlLCBzaXplb2Yoc2hvcnQgaW50KSpNQVgpOwoJCW1lbXNldChtYXhIZWlnaHQsIDAsIHNpemVvZihpbnQpKk1BWCk7CgkJREZTKHRyZWUsIGN1cnJlbnRMZWFmLCBuKTsgICAgICAgICAgICAgIAoKCQlmb3IgKCBpPTE7IGk8PW47IGkrKyApIHsKCQkJCWlmICggbWF4TGVuIDwgbWF4SGVpZ2h0W2ldICkgewoJCQkJCQltYXhMZW4gPSBtYXhIZWlnaHRbaV07CgkJCQkJCWN1cnJlbnRMZWFmID0gaTsKCQkJCX0KCQl9CgoJCWlmICggMCA9PSBtYXhMZW4gJSAyICkgeyAgICAgICAgICAgICAgICAvKiBvbmx5IG9uZSByb290IG5vZGUgKi8KCQkJCWZvciAoIGk9MTsgaTw9biA7IGkrKyApIHsKCQkJCQkJaWYgKCBtYXhMZW4vMiA9PSBtYXhIZWlnaHRbaV0gICl7CgkJCQkJCQkJYmVzdE5vZGVbYmVzdE5vZGVUb3BdID0gaTsKCQkJCQkJCQliZXN0Tm9kZVRvcCArPSAxOwoJCQkJCQl9CgkJCQl9CgkJCQltZW1zZXQodmlzaXRlZCwgRmFsc2UsIHNpemVvZihzaG9ydCBpbnQpKk1BWCk7CgkJCQltZW1zZXQobWF4SGVpZ2h0LCAwLCBzaXplb2YoaW50KSpNQVgpOwoJCQkJZGZzRm9yTGVhZih0cmVlLCBiZXN0Tm9kZVswXSwgbiwgMCk7CgoJCQkJZm9yICggaT0xOyBpPD1uIDsgaSsrICkgewoJCQkJCQlpZiAoIG1heExlbi8yID09IG1heEhlaWdodFtpXSAgKXsKCQkJCQkJCQl3b3JzdE5vZGVbd29yc3ROb2RlVG9wXSA9IGk7CgkJCQkJCQkJd29yc3ROb2RlVG9wICs9IDE7CgkJCQkJCX0KCQkJCX0KCQl9CgkJZWxzZSB7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8qIHR3byBiZXN0IG5vZGVzICovCgkJCQlmb3IgKCBpPTE7IGk8PW4gOyBpKysgKSB7CgkJCQkJCWlmICggbWF4TGVuLzIgPT0gbWF4SGVpZ2h0W2ldIHx8IChtYXhMZW4vMikrMSA9PSBtYXhIZWlnaHRbaV0gKSB7CgkJCQkJCQkJYmVzdE5vZGVbYmVzdE5vZGVUb3BdID0gaTsKCQkJCQkJCQliZXN0Tm9kZVRvcCArPSAxOwoJCQkJCQl9CgkJCQl9CgoJCQkJZm9yICggaT1iZXN0Tm9kZVRvcC0xOyBpPj0wIDsgaS0tICkgeyAvKiBnZXQgdGhlIHdvcnN0IG5vZGVzICovCgkJCQkJCW1lbXNldCh2aXNpdGVkLCBGYWxzZSwgc2l6ZW9mKHNob3J0IGludCkqTUFYKTsKCQkJCQkJbWVtc2V0KG1heEhlaWdodCwgMCwgc2l6ZW9mKGludCkqTUFYKTsKCQkJCQkJZGZzRm9yTGVhZih0cmVlLCBiZXN0Tm9kZVtpXSwgbiwgMCk7CgoJCQkJCQlmb3IgKCBqPTE7IGo8PW4gOyBqKysgKSB7CgkJCQkJCQkJaWYgKCAxKyhtYXhMZW4vMikgPT0gbWF4SGVpZ2h0W2pdICApewoJCQkJCQkJCQkJd29yc3ROb2RlW3dvcnN0Tm9kZVRvcF0gPSBqOwoJCQkJCQkJCQkJd29yc3ROb2RlVG9wICs9IDE7CgkJCQkJCQkJfQoJCQkJCQl9CgkJCQl9CgoJCX0KCgkJcHJpbnRmICggIkJlc3QgUm9vdHMgIDoiICk7CgkJZm9yICggaT0wOyBpPGJlc3ROb2RlVG9wIDsgaSsrICkgewoJCQkJcHJpbnRmICggIiAlZCIsIGJlc3ROb2RlW2ldICk7CgkJfQoKCQlwcmludGYgKCAiXG5Xb3JzdCBSb290cyA6IiApOwoJCWZvciAoIGk9MDsgaTx3b3JzdE5vZGVUb3AgOyBpKysgKSB7CgkJCQlwcmludGYgKCAiICVkIiwgd29yc3ROb2RlW2ldICk7CgkJfQoJCXJldHVybiA7Cn0JCS8qIC0tLS0tICBlbmQgb2YgZnVuY3Rpb24gZmluZEJlc3RSb290ICAtLS0tLSAqLwoKLyogCiAqID09PSAgRlVOQ1RJT04gID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KICogICAgICAgICBOYW1lOiAgREZTCiAqICBEZXNjcmlwdGlvbjogIAogKiA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CiAqLwoJCWludApERlMgKCBOb2RlIHRyZWVbXSwgaW50IHcsIGludCBuICkKewoJCWludCBpID0gMSwgbWF4PS0xOwoJCU5vZGUgKnBvaW50ZXIgPSBOVUxMOwoJCXZpc2l0ZWRbd10gPSBUcnVlOwoJCWZvciAoIHBvaW50ZXIgPSB0cmVlW3ddLm5leHQgOyBOVUxMICE9IHBvaW50ZXIgOyBwb2ludGVyPXBvaW50ZXItPm5leHQgKSB7CgkJCQlpZiAoICF2aXNpdGVkWyBwb2ludGVyLT5pZCBdICkgewoJCQkJCQlpID0gREZTKHRyZWUsIHBvaW50ZXItPmlkLCBuKTsKCQkJCQkJaWYgKCBtYXggPCBpICkgeyAgICAgICAgLyogdGhlIGVuZHBvaW50IG9mIGxvbmdlciBwYXRoICovCgkJCQkJCQkJbWF4ID0gaTsKCQkJCQkJCQl0cmVlW3ddLndoaWNoID0gdHJlZVtwb2ludGVyLT5pZF0ud2hpY2g7CgkJCQkJCX0KCQkJCX0KCQl9CgkJbWF4SGVpZ2h0W3ddICs9ICggbWF4KzEgKTsKCQkKCQlpZiAoIDAgPT0gbWF4SGVpZ2h0W3ddICkKCQkJdHJlZVt3XS53aGljaCA9IHc7CgkJcmV0dXJuIG1heEhlaWdodFt3XTsKfQkJLyogLS0tLS0gIGVuZCBvZiBmdW5jdGlvbiBERlMgIC0tLS0tICovCi8qIAogKiA9PT0gIEZVTkNUSU9OICA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CiAqICAgICAgICAgTmFtZTogIG1haW4KICogIERlc2NyaXB0aW9uOiAgCiAqID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KICovCgkJaW50Cm1haW4gKCBpbnQgYXJnYywgY2hhciAqYXJndltdICkKewoJCWludCBpID0gMCwgaiA9IDA7ICAgICAgICAgICAgICAgICAgICAgICAvKiBjb3VudGVyICovCgkJaW50IG4gPSAwLCB0ID0gMCwgayA9IDA7ICAgICAgICAgICAgICAgIC8qIHRlbXAgdmFyaWFibGUgKi8KCQlpbnQgcm9vdElkID0gMDsKCQlpbnQga25vd25sZWFmID0gMDsKCQlOb2RlIG5vZGVMaXN0W01BWCsxXTsKCQlOb2RlICp0ZW1wID0gTlVMTCwgKmhlYWQ9TlVMTCwgKnRhaWw9TlVMTDsgICAgICAgICAgLyogdGVtcCB2YXJpYWJsZSAqLwoKCQl3aGlsZSAoIEVPRiAhPSBzY2FuZigiJWQiLCAmbikgKSB7ICAgICAgLyogdG90YWwgbm9kZXMgKi8KCQkJCQoJCQkJZm9yICggaSA9IDE7IGkgPD0gbiA7IGkrKyApIHsKCQkJCQkJaGVhZCA9IHRlbXAgPSBOVUxMOwoJCQkJCQlub2RlTGlzdFtpXS5kZXB0aCA9IDA7CgkJCQkJCXNjYW5mICggIiVkIiwgJnQgKTsgICAgIC8qIG5laWdoYm9yIGFtb3VudHMgKi8KCQkJCQkJZm9yICggaj0wOyBqIDwgdCA7IGorKyApIHsKCQkJCQkJCQlzY2FuZiAoICIlZCIsICZrICk7CgkJCQkJCQkJaWYgKCBOVUxMID09IGhlYWQgICkgewoJCQkJCQkJCQkJaGVhZCA9IChOb2RlKiltYWxsb2Moc2l6ZW9mKE5vZGUpKTsKCQkJCQkJCQkJCWhlYWQtPmlkID0gazsKCQkJCQkJCQkJCWhlYWQtPmRlcHRoID0gMDsKCQkJCQkJCQkJCWhlYWQtPndoaWNoID0gLTE7CgkJCQkJCQkJCQl0YWlsID0gaGVhZDsKCQkJCQkJCQl9CgkJCQkJCQkJZWxzZSB7CgkJCQkJCQkJCQl0ZW1wID0gKE5vZGUqKW1hbGxvYyhzaXplb2YoTm9kZSkpOwoJCQkJCQkJCQkJdGVtcC0+aWQgPSBrOwoJCQkJCQkJCQkJdGVtcC0+bmV4dCA9IE5VTEw7CgkJCQkJCQkJCQl0ZW1wLT5kZXB0aCA9IDA7CgkJCQkJCQkJCQloZWFkLT53aGljaCA9IC0xOwoJCQkJCQkJCQkJdGFpbC0+bmV4dCA9IHRlbXA7CgkJCQkJCQkJCQl0YWlsID0gdGVtcDsKCQkJCQkJCQl9CgkJCQkJCQkJbm9kZUxpc3RbaV0uZGVwdGggKz0gMTsKCQkJCQkJfQoJCQkJCQlub2RlTGlzdFtpXS5uZXh0ID0gaGVhZDsKCQkJCX0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLyogaW5pdGlhbCAqLwoJCQkJbWVtc2V0KHZpc2l0ZWQsIEZhbHNlLCBzaXplb2Yoc2hvcnQgaW50KSpNQVgpOwoJCQkJZm9yICggaT0xOyBpPD1uIDsgaSsrICkKCQkJCQkJbWF4SGVpZ2h0W2ldID0gIDA7CgoJCQkJCQoJCQkJZm9yICggaT0xOyBpPD1uIDtpKysgKSB7ICAgICAgICAvKiBmaW5kIGEgbGVhZiBub2RlIGFuZCBnbyBERlMgZnJvbSBoaW0gKi8KCQkJCQkJaWYgKCAxID09IG5vZGVMaXN0W2ldLmRlcHRoICkgewoJCQkJCQkJCWtub3dubGVhZiA9IGk7CgkJCQkJCQkJYnJlYWs7CgkJCQkJCX0KCQkJCX0KCQkJCQoJCQkJZmluZEJlc3RSb290KCBub2RlTGlzdCwga25vd25sZWFmLCBuKTsKCQl9CgoJCXJldHVybiBFWElUX1NVQ0NFU1M7Cn0JCQkJLyogLS0tLS0tLS0tLSAgZW5kIG9mIGZ1bmN0aW9uIG1haW4gIC0tLS0tLS0tLS0gKi8=