nyoj 211&&poj 3660

Cow Contest

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a PRogramming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

5 54 34 23 21 22 50 0样例输出
2
////能打败的个数加上被打败的个数恰好等于n-1,则能确定,////否则无法确定,抽象为简单的floyd传递闭包算法,////在加上每个顶点的出度与入度 (出度+入度=顶点数-1,则能够确定其编号)。#include<queue>#include<stack>#include<vector>#include<math.h>#include<stdio.h>#include<numeric>//STL数值算法头文件#include<stdlib.h>#include<string.h>#include<iostream>#include<algorithm>#include<functional>//模板类头文件using namespace std;const int INF=1e9+7;const int maxn=102;int n,m;int tu[maxn][maxn];int main(){    int i,j,k,x,y,ans;    while(~scanf("%d %d",&n,&m),n+m)    {        memset(tu,0,sizeof(tu));        while(m--)        {            scanf("%d %d",&x,&y);            tu[x][y]=1;        }        for(k=1; k<=n; k++)            for(i=1; i<=n; i++)                for(j=1; j<=n; j++)                    if(tu[i][k]&&tu[k][j])                        tu[i][j]=1;        int ans=0;        for(i=1; i<=n; i++)        {            int cont=n-1;            for(j=1; j<=n; j++)                if(tu[i][j]||tu[j][i])                    cont--;            if(!cont)                ans++;        }        printf("%d/n",ans);    }    return 0;}