The Happy Desert is full of sands. There is only a kind of
animal called camel living on the Happy Desert. Cause they live here,
they need water here. Fortunately, they find a pond which is full of
water in the east corner of the desert. Though small, but enough.
However, they still need to stand in lines to drink the water in the
pond.
Now we mark the pond with number 0, and each of the camels with a
specific number, starting from 1. And we use a pair of number to show
the two adjacent camels, in which the former number is closer to the
pond. There may be more than one lines starting from the pond and ending
in a certain camel, but each line is always straight and has no forks.
There’re multiple test cases. In each case, there is a number N
(1≤N≤100000) followed by N lines of number pairs presenting the
proximate two camels. There are 99999 camels at most.
For each test case, output the camel’s number who is standing
in the last position of its line but is closest to the pond. If there
are more than one answer, output the one with the minimal number.
#include <stdio.h>
int uset[100000];
void u_init(){
int i;
for(i=0; i<100000; i++){
uset[i] = -1;
}
}
void u_merge(int r1, int r2){
uset[r1] = r2;
}
void main(){
int lines,a,b,ra,rb,min;
int stack[100000];
int top = -1;
while(scanf(" %d", &lines) != EOF){
u_init();
while(lines--){
scanf(" %d %d", &a, &b);
if(a == 0){
stack[++top] = b;
continue;
}
u_merge(a, b);
}
min = 100000;
while(top>=0){
a = stack[top--];
b = 0;
while(uset[a] >= 0){
a = uset[a];
b++;
}
if(b==min){
if(a < ra){
ra = a;
}
}else if(b<min){
min = b;
ra = a;
}
}
printf("%d\n", ra);
}
}