2218.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2218 on 2006-04-26 at 12:29:12 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int BN = 256;

int main()
{
	bool need[BN][BN];
	int u[BN], d[BN];
	int t, T, i, j, k;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n, m; scanf("%d %d", &n, &m);
		memset(need, false, sizeof(need));
		for(i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			need[a-1][b-1] = true;
		}
		for(k = 0; k < n; k++)
			for(i = 0; i < n; i++)
				for(j = 0; j < n; j++)
					need[i][j] = need[i][j] || (need[i][k] && need[k][j]);
		for(i = 0; i < n; i++) u[i] = 1, d[i] = n;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(need[i][j]) d[i]--, u[j]++;
		int cnt = 0, mid = (n+1)/2;
		for(i = 0; i < n; i++)
			if(u[i] > mid || d[i] < mid) cnt++;
		printf("%d\n", cnt);
	}
	
	return 0;
}