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.
Input* Line 1: Two space-separated integers: N and M* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
Output* Line 1: A single integer representing the number of cows whose ranks can be determined
Sample Input 5 5 4 3 4 2 3 2 1 2 2 5 Sample Output2
题目就是要你求出有多少头奶牛可以确定它的排名
我用的floyed，但是它的复杂度太大O(N^3);只是合用在数据比较少的…………
#include<map>#include<stdio.h>#include<string>#include<string.h>#include <iostream>#include<algorithm>using namespace std;int main(){ int n,m,t1,t2,sum=0; scanf("%d%d",&n,&m); int a[102][102]; memset(a,0,sizeof(a)); int ans[102]; memset(ans,0,sizeof(ans)); for(int i=0;i<m;i++) { scanf("%d%d",&t1,&t2); a[t1][t2]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i!=j&&!a[i][j]) { a[i][j]=a[i][k]&&a[k][j];//判断两头牛之间是否可以分出排名 } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]) { ans[i]++; ans[j]++; } } } for(int i=1;i<=n;i++) { if(ans[i]==n-1)//如果和n-1头牛都可以确定关系，符合 { sum++; } } printf("%d\n",sum);}
