http://poj.org/problem?id=2580
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int k[20],keys[20][200],to[20][200];
int key[20];
int n,begin;
bool init()
{
char w[100],num[100],t;
int i,j,h;
scanf( "%s", w );
if( strcmp( "ENDOFINPUT", w ) == 0 )
return false;
scanf( "%d %d", &begin, &n );
getchar();
for( i=0; i<n; i++ )
{
k[i] = 0;
while(1)
{
j=0;
while(1)
{
t = getchar();
if( t >= '0' && t <= '9' ) num[j++] = t;
else break;
}
num[j] = '';
to[i][ k[i] ] = atoi( num );
keys[i][ k[i] ] = 0;
while( t <= 'Z' && t >= 'A' )
{
keys[i][ k[i] ] |= 1 << (t-'A');
t = getchar();
}
if(j)k[i]++;
if( t == 'n' ) break;
}
}
for( i=0; i<n; i++ )
{
key[i] = 0;
do
{
t = getchar();
if( t <= 'Z' && t >= 'A' ) key[i] |= 1 << (t-'A');
}while( t != 'n' );
}
scanf( "%s", w );
for( i=0; i<n; i++ )
{
for( j=0; j<k[i] && (h=to[i][j]) > i; j++ )
{
to[ h ][ k[h] ] = i;
keys[ h ][ k[h] ] = keys[i][j];
k[h]++;
}
}
return true;
}
int KEY;
bool sign[20];
bool search( int s )
{
int i;
sign[s] = true;
if( s == 0 ) return true;
if( ( KEY | key[s] ) != KEY )
{
KEY |= key[s];
return true;
}
for( i=0; i<k[s]; i++ )
if( !sign[ to[s][i] ] && ( KEY | keys[s][i] ) == KEY )
{
if( search( to[s][i] ) ) return true;
}
return false;
}
void doit()
{
int i;
KEY = 0;
while( 1 )
{
for( i=0; i<n; i++)
sign[i] = false;
if( !search( begin ) )
{
printf( "NOn" );
return;
}
if( sign[0] == true )
{
printf( "YESn" );
return;
}
}
}
int main()
{
while(init())
doit();
return 0;
}