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.

Leave a Reply

Your email address will not be published. Required fields are marked *