1975.txt

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

#include<stdio.h>
#include<string.h>
#define debug 0
#define NMAX 104
#define INF 1000
int a[NMAX][NMAX];
int b[NMAX][NMAX];
int f[NMAX][2];
int N,M;

main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
    int i,j,t;
    int x,y,u,v,w;
    int count;
    int ano,bno;
    scanf("%d",&t);
    while(t--)
    {
        
        scanf("%d%d",&N,&M);
        memset(a,0,(NMAX)*(NMAX)*sizeof(int));
        memset(b,0,(NMAX)*(NMAX)*sizeof(int));
        memset(f,-1,(NMAX)*2*sizeof(int));
        for(i=0;i<M;i++)
        {
            scanf("%d%d",&x,&y);
            a[x][y]=1;
            b[y][x]=1;
        }
        for(u=1;u<=N;u++)
			for(v=1;v<=N;v++)
				for(w=1;w<=N;w++)
				{
 					if(a[v][u]*a[u][w]==1)
					{
						a[v][w]=1;
    				}
    				if(b[v][u]*b[u][w]==1)
					{
						b[v][w]=1;
    				}
				}
        count=0;
        for(i=1;i<=N;i++)
        {
            ano=0;bno=0;
            for(j=1;j<=N;j++)
            {
                if(a[i][j]==1)
                    ano++;
                if(b[i][j]==1)
                    bno++;
            }
            if(ano>=(N+1)/2||bno>=(N+1)/2)
                count++;
            
        }
        printf("%d\n",count);
    }
        
            
    

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}