FJ想按照奶牛产奶的能力给她们排序。现在已知有N头奶牛（1 ≤ N ≤ 1,000）。FJ通过比较，已经知道了M（1 ≤ M ≤ 10,000）对相对关系。每一对关系表示为“X Y”，意指X的产奶能力强于Y。现在FJ想要知道，他至少还要调查多少对关系才能完成整个排序。
这道题和Floyd--P2419 [USACO08JAN]牛大赛Cow Contest 有异曲同工之妙啊，但是2419我用的是floyd，对于n^3的做法，本题的数据范围n<=1000显然只能得到部分分（并不会bitset优化）：
先说说floyd的60分作法：考虑我们如何能确定一头牛的排名？即本牛和其他所有牛的关系都确定。
1：预处理：输入a和b，s[a][b]=1表示a赢了b
2：floyd：如果i赢了t，t赢了j，i就赢了j（t可以看做一个中转接点）
3：统计答案：如果俩头牛有一头赢了，那么另一头就输了，俩头牛的关系确定，而他不会自我矛盾，所以如果判断到两头牛没有一头赢，那么两头牛的关系不确定，答案+1，然后标记两头牛的关系确定（否则答案会重复）
代码：
1 #include <cstdio>
2 #include <algorithm>
3 #include <cmath>
4 #include <iostream>
5 #include <cstring>
6 using namespace std;
7 int n,m,a,b;
8 int s[10005][10005];
9 void Floyd(){
10 for (int t = 1;t <= n;t++){
11 for (int i = 1;i <= n;i++){
12 for (int j = 1;j <= n;j++){
13 if (s[i][t]&&s[t][j])
14 s[i][j]=1;
15 }
16 }
17 }
18 }
19 int main(){
20 int ans=0;
21 scanf ("%d%d",&n,&m)
22 for (int i = 1;i <= m;i++) {
23 scanf ("%d%d",&a,&b);
24 s[a][b]=1;
25 }
26 Floyd();
27 for(int i = 1;i <= n;i++){
28 for (int j = 1;j <= n;j++){
29 if (i==j)continue;
30 if (s[i][j]==0&&s[j][i]==0){
31 ans++;
32 s[i][j]=1;
33 }
34 }
35 }
36 cout<<ans;
37 return 0;
38 }
拓扑作法：
1.预处理：构建一个图，从一头牛（节点）可以走到被他打败的牛（节点） f[a][b]=1，a打败了b，degree[b]++（被打败的牛（节点）的入度+1）
2.bfs（拓扑）：从一个入度为0的节点出发（没有被打败过），由于我们我们构建的一个图，他的性质为当前节点打败了他的子节点，那么当前节点也打败了他子节点的子节点 if(f[i][x])f[i][edge[k].to]=1 把子节点的入度减一
3.统计答案：如果俩头牛有一头赢了，那么另一头就输了，俩头牛的关系确定，而他不会自我矛盾，所以如果判断到两头牛没有一头赢，那么两头牛的关系不确定，答案+1，然后标记两头牛的关系确定（否则答案会重复）
代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e3+5;
4 struct node{int to,next;}edge[N*10];
5 int head[N],tot,degree[N];
6 bool f[N][N],vis[N],in[N];
7 int n,m,x,y,z,ans;
8 void add(int x,int y){
9 edge[++tot].to=y;
10 edge[tot].next=head[x];
11 head[x]=tot;
12 }
13 void bfs(){
14 queue<int>Q;
15 for(int i=1;i<=n;i++)if(!degree[i])Q.push(i);
16 while(!Q.empty()){
17 int x=Q.front();Q.pop();vis[x]=1;
18 for(int k=head[x];k;k=edge[k].next){
19 if(vis[edge[k].to])continue;
20 for(int i=1;i<=n;i++)if(f[i][x])f[i][edge[k].to]=1;
21 degree[edge[k].to]--;
22 if(degree[edge[k].to]==0)Q.push(edge[k].to);
23 }
24 }
25 }
26 int main(){
27 scanf("%d%d",&n,&m);
28 for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x,y),f[x][y]=1,degree[y]++;
29 bfs();
30 for(int i=1;i<=n;i++){
31 for(int j=1;j<=n;j++)if(!f[i][j]&&!f[j][i]&&i!=j)ans++,f[i][j]=1;
32 }
33 printf("%d",ans);
34 }