poj1975

#include<stdio.h>

#include<string.h>

#define N 100

int map[N][N];

int main() {

int t,n,m,i,j,k,sum1,sum2,total,mid,a,b;

scanf("%d",&t);

while(t–) {

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

memset(map,0,sizeof(map));

while(m–) {

scanf("%d%d",&a,&b);

map[a][b]=1;map[b][a]=-1;

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {

if(map[i][k]==1&&map[k][j]==1)

map[i][j]=1;

if(map[i][k]==-1&&map[k][j]==-1)

map[i][j]=-1;

}

total=0;mid=(n+1)/2;

for(i=1;i<=n;i++) {

sum1=0;sum2=0;

for(j=1;j<=n;j++) {

if(map[i][j]==1)

sum1++;

if(map[i][j]==-1)

sum2++;

}

if(sum1>=mid||sum2>=mid)

total++;

}

printf("%d\n",total);

}

return 0;

}