/*

本题的题意:

沙漠中有很多骆驼和一个池塘,0表示池塘,1-N表示骆驼,
输入的两个数表示两只骆驼,其中前面的那一头靠近池塘,
所有的骆驼队列不交叉不相连,求站在队尾但是离水井最近的骆驼编号

经过分析最后还是要先构造一个树,然后寻找离0最近的一个点,当结果是相等的级别的时候将结果返回最小的那个值

*/

参考代码:

 #include<stdio.h>
#include<string.h>
#define maxn 100010 int pre[maxn], dis[maxn];
//pre 数组代表当前骆驼的前一个骆驼, dis 数组代表当前骆驼到水井的距离
int main()
{
int n;
while(scanf("%d", &n) != EOF){
int x, y, i, ans, mind;
memset(dis, , sizeof(dis));
//父节点初始化 并查集必备
for(i = ; i < n; i++)
pre[i] = i;
for(i = ; i < n; i++){
scanf("%d %d", &x, &y);
pre[y] = x;
dis[x] = ;
}
for(mind = n + , ans = i = ; i <= n; i++){//注意:mind的初始值要大于n
//如果dis[i]为0 即该节点无子节点
if(!dis[i]){
x = i; //x 是一个临时变量
//如果这个节点有父节点 递归求出距离
while(pre[x] != x){
x = pre[x];
dis[i]++;
}
//找出最大距离所在的骆驼
if(!x && dis[i] < mind){
mind = dis[i];
ans = i;
}
}
}
printf("%d\n", ans);
}
return ;
}
05-04 05:34