农夫约翰的N头奶牛（1≤N≤1000）产奶率各不相同，FJ希望根据这些比率从最快的奶牛到最慢的奶牛订购奶牛。 FJ已经比较了M（1≤M≤10000）对奶牛的产奶率。他想列出另外C对奶牛的列表，这样，如果他现在比较这些C对奶牛，他肯定能够推断出所有N头牛的正确顺序。请帮助他确定C的最小值，这样的列表是可能的。
输入 第1行：两个空格分隔的整数：N和M 第2..M+1行：分别是两个空格分隔的整数：X和Y。X和Y都在1…N的范围内，并描述了奶牛X的排名高于奶牛Y的比较。 输出 第1行：一个整数，是C的最小值。
Sample Input 5 5 2 1 1 5 2 3 1 4 3 4 Output 3
思路
根据排列组合易知，总关系数目为n * (n - 1) / 2。用一个位集合记录大小关系。大小关系具有传递性，若a > b > c，则必有a > c。通过这一结论，利用按位或运算，推断隐含的大小关系。最后统计已知的关系数目，用总关系数目减去已知关系数目得到待求关系数目。
AC代码
#include <iostream>
#include <bitset>
using namespace std;
#define AUTHOR "HEX9CF"
bitset<1005> bs[1005];
int main()
{
int n, m;
int cnt = 0;
cin >> n >> m;
int c = n * (n - 1) / 2;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
bs[a][b] = 1;
}
for (int j = 1; j <= n; j++)
{
for (int i = 1; i <= n; i++)
{
// a > b, b > c
if (bs[i][j])
{
// a > c
bs[i] |= bs[j];
}
}
}
for (int i = 1; i <= n; i++)
{
cnt += bs[i].count();
// cout << bs[i].count() << endl;
}
// cout << cnt << endl;
cout << c - cnt << endl;
return 0;
}