2186.txt

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

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

using namespace std;

vector<int> e[10000];
vector<int> h[10000];

bool sign[10000];
int n, m, reach;

void search( int s,vector<int> e[10000] )
{
	vector<int>::iterator i;

	sign[s] = true;
	reach++;
	
	for( i=e[s].begin(); i != e[s].end(); i++ )
	if( !sign[*i] )
	search( *i, e );

}

void init()
{
	int i, a, b, k;

	scanf( "%d %d", &n, &m );

	for( i=0; i<n; i++ )
	e[i].clear();

	for( i=0; i<m; i++ )
	{
		scanf( "%d %d", &a, &b );
		e[a-1].push_back(b-1);
		h[b-1].push_back(a-1);
	}

	
}

int doit()
{
	int i, r;

	memset( sign, 0, sizeof(sign) );
	r = 0;reach = 0;
	
	for( i=0; i<n; i++ )
	if( !sign[i] )
	{
		r = i;
		search( i, h );
	}

	reach = 0;
	memset( sign, 0, sizeof(sign) );

	search( r, h );
	if( reach != n ) return 0;

	reach = 0;
	memset( sign, 0, sizeof(sign) );
	search( r, e );

	return reach;
}

int main()
{
	init();
	printf( "%d\n", doit() );

	return 0;
}