CSUOJ 1010:Water Drinking
2769 ワード
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1010
この問題は一つのチームの最後のラクダの番号を見つけたいです。チームの要求は二つあります。
1.ラクダの数が一番少ない
2.池につながる
この問題は一つのチームの最後のラクダの番号を見つけたいです。チームの要求は二つあります。
1.ラクダの数が一番少ない
2.池につながる
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXN 100005
int next[MAXN], s[MAXN];
int N, top, k;
int main()
{
while( scanf( "%d", &N) == 1)
{
int n = N;
top = 0;
memset( next, -1, sizeof next);
while( n --)
{
int a, b;
scanf( "%d%d", &a, &b);
if( a == 0) s[top ++] = b;
else
next[a] = b;
}
int min = MAXN;
for( int i = 0; i < top; i ++)
{
int ans = 1, t, j;
j = s[i];
while( j != -1)
{
ans ++;
t = j;
j = next[j];
}
if( ans < min ) {
min = ans;
k = t;
}
if( ans == min && t < k)
k = t;
}
printf( "%d
", k);
}
return 0;
}