【POJ 3275】Ranking the Cows 题解（传递闭包）

农夫约翰的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;
}