3217.txt

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

#include <stdio.h>
#include <memory.h>
#include <vector>

using namespace std;

vector<int> ch[101];
int father[101], mother[101];
bool gender[101];
int A, B;

void input( ) {
	int i, h, t;

	scanf( "%d%d", &A, &B );
	for( i=0; i<101; i++ )
		ch[i].clear( );
	
	while( true ) {
		if( scanf( "%d", &h ) != 1 )
			break;

		while( true ) {
			scanf( "%d", &t );
			if( t <= 0 ) {
				gender[h] = (t==0);
				break;
			}
			ch[h].push_back( t );
		}
		
		for( i=0; i<ch[h].size(); i++ )
			if( gender[h] )
				father[ ch[h][i] ] = h;
			else
				mother[ ch[h][i] ] = h;
	}
	return;
}

void fill( vector<int> &s, int p, int LIMIT ) {
	int a, b = 0, i, k;
	
	s.push_back( p );

	for( k=0; k<LIMIT; k++ ) {
		a = b;
		b = s.size();
		for( i=a; i<b; i++ ) {
			if( father[s[i]] )
				s.push_back( father[s[i]] );
			if( mother[s[i]] )
				s.push_back( mother[s[i]] );
		}
	}

}

void check( ) {
	int i, j;

	if( gender[A] == gender[B] ) {
		printf( "same\n" );
		return;
	}

	vector<int> sa, sb;

	fill( sa, A, 2 );
	fill( sb, B, 2 );

	for( i=0; i<sa.size(); i++ ) {
		for( j=0; j<sb.size(); j++ ) {
			if( sa[i] == sb[j] ) {
				printf( "close\n" );
				return;
			}
		}
	}


	sa.clear( );
	fill( sa, A, 100 );
	for( i=0; i<sa.size(); i++ )
		if( sa[i] == B ) {
			printf( "close\n" );
			return;
		}

	sb.clear( );
	fill( sb, B, 100 );
	for( i=0; i<sb.size(); i++ )
		if( sb[i] == A ) {
			printf( "close\n" );
			return;
		}
	printf( "marriage\n" );
	return ;
}

int main( ) {
	input( );
	check( );
	return 0;
}