# Poj Solution 1612

```http://poj.org/problem?id=1612

#include<iostream>
using namespace std;

int dis[50][50],n;

void init()
{
char c;
int i,j,k;

cin>>n;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
dis[i][j]=9999;
dis[i][i]=0;
}

for(i=0;i<n;i++)
{
cin.get(c);
while(cin.peek()!='n')
{
cin>>j;

dis[i][j-1]=1;
dis[j-1][i]=1;
}

}

for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dis[i][k]<9999&&dis[k][j]<9999&&dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];

}

void doit()
{
int m,v[100],i,j,d,k;
bool sign[100];
char c;

cin>>m;

while(m--)
{
for(i=0;i<n;i++)
sign[i]=0;

i=0;
if(cin.peek()=='n')
cin.get(c);
while(cin.peek()!='n')
{
cin>>v[i];
if(cin.fail())break;
v[i]--;

if(v[i]<n&&sign[v[i]]==0)
{
sign[v[i]]=1;
i++;
}

}
d=i;

for(i=0;i<n;i++)
{
for(j=0;j<d&&sign[i]==0;j++)
for(k=0;k<d;k++)
if(dis[v[j]][i]+dis[i][v[k]]==dis[v[j]][v[k]]&&dis[v[j]][v[k]]<9999)
{
sign[i]=1;
break;
}
}

for(i=0;i<n;i++)
if(!sign[i])break;

if(i>=n)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}

}

int main()
{
init();
doit();
return 0;
}
```
This entry was posted in poj. Bookmark the permalink.