1904.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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;
}