2890.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 71 行

Problem Id:2890  User Id:fzk 
Memory:140K  Time:343MS
Language:C++  Result:Accepted

Source 

//#include <functional>
//#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

vector<int> e[1000];
stack<int> sk;

int sign[1000] = { 0 };
int count = 0;
int c;

int n, m;
bool input() {
	int i, a, b;
	if( scanf( "%d%d", &n, &m ) != 2 )
		return false;
		
	for( i=0; i<n; i++ ) {
		e[i].clear( );
	}
	
	for( i=0; i<m; i++ ) {
		scanf( "%d%d", &a, &b );
		e[a].push_back( b );
	}
	return true;
}

void travel( int k ) {
	int i;
	c++;
	sign[k] = count;
	for( i=0; i<e[k].size(); i++ )
		if( sign[ e[k][i] ] != count )
			travel( e[k][i] );
		
} 
		

int doit() {
	int ans = 0, i;
	for( i=0; i<n; i++ ) {
		count++;
		c=0;
		travel( i );
		ans += c;
	}
	return ans;
}

int main( ) {
	while( input() ) {
		printf( "%d\n", doit() );
	}
	return 0;
}