# Poj Solution 1904

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

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int e2[2010], ee2[2010], n;
vector<int> e1[2010];
vector<int> ee1[2010];

vector<int> ans[2010];

void input( ) {
int i, k, m;
scanf( "%d", &n );

for( i=0; i<n; i++ ) {
scanf( "%d", &m );
e1[i].resize( m );
while( m-- ) {
scanf( "%d", &k );
e1[i][m] = k-1;
ee1[k-1].push_back( i );
}
}

for( i=0; i<n; i++ ) {
scanf( "%d", &e2[i] );
e2[i]--;
ee2[e2[i]] = i;
}

}

vector<int> st;
int st2[2010], sn2;

bool sign[2010];
int flag1[2010], flag2[2010], counter;

void search( int k ) {
int s = ee2[k];
sign[k] = true;
for( int i=0; i<e1[s].size(); i++ )
if( !sign[e1[s][i]] )
search( e1[s][i] );
st.push_back( k );
}

void dfs1( ) {
for( int i=0; i<n; i++ )
if( !sign[i] )
search( i );
}

void find( int k ) {
int t;
flag1[k] = counter;
for( int i=0; i<ee1[k].size(); i++ ) {
t = ee1[k][i];
if( !flag2[t] ) {
st2[sn2++] = t;
flag2[t] = counter;
if( !flag1[ e2[t] ] )
find( e2[t] );
}
}
}

void dfs2( ) {
int t;
for( int i=n-1; i>=0; i-- ) {
if( !flag1[st[i]] ) {

sn2 = 0;
counter = i+1;
find( st[i] );

while( sn2-- ) {
t = st2[sn2];
for( int j=0; j<e1[t].size(); j++ )
if( flag1[e1[t][j]] == counter )
ans[t].push_back( e1[t][j] );
sort( ans[t].begin(), ans[t].end() );
}
}
}
}

void output( ) {
for( int i=0; i<n; i++ ) {
printf( "%d", ans[i].size() );
for( int j=0; j<ans[i].size(); j++ )
printf( " %d", ans[i].operator [](j)+1 );
printf( "n" );
}

}

int main( ) {
input( );
dfs1();
dfs2();
output( );
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.