[UVa] 10227 - Forests

題目網址: http://goo.gl/PHGxpD

題意:
(from luckycat)


解 法: 暴力檢查。

TAG: Brute Force,

注意:

程式碼:

	/**
	* Tittle: 10227 - Forests
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/22
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	// declarations
	int t;
	int ppl, tree;
	bool canSee[N][N];
	// functions
	bool check( int u, int v )
	{
	FOR( i, 1, tree )
	if( canSee[u][i] != canSee[v][i] )
	return false;
	return true;
	}
	// main function
	int main( void )
	{
	char buf[N];
	bool vis[N];
	int u, v;
	int cnt;
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d%d", &ppl, &tree );
	gets( buf );
	clr( canSee, false );
	while( gets(buf) && strcmp(buf,"") ) {
	sscanf( buf, "%d%d", &u, &v );
	canSee[u][v] = true;
	}
	// solve
	clr( vis, false );
	cnt = 0;
	FOR( i, 1, ppl ) if( !vis[i] ) {
	FOR( j, i+1, ppl ) if( !vis[j] )
	if( check(i,j) )
	vis[j] = true;
	++cnt;
	}
	printf( "%d\n", cnt );
	if( t ) putchar('\n');
	}
	return 0;
	}

view raw 10227 - Forests.cpp hosted with ❤ by GitHub