POJ3275 Ranking the Cows

题意：
有N个数字，已经比较了M对(x,y),其中x>y, 问至少再需要比较多少对数字，就能
把N个数按大小有序的排列起来

分析：
如果x>y,就在x和y之间连一条单向边，然后用floyd算法（floyd传递闭包），

AC代码：

#include <bitset>
#include <cstdio>

using namespace std;

int n, m, a, b, ans;
bitset<1005> bi[1005];//要用bitset来存01矩阵，可以省掉最外面的一层for循环，不然会超时
//bi[i][j] = 1,表示i和j相连（大小确定）

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &a, &b);
        bi[a][b] = 1;
        //注意是单向边，只需要bi[a][b] = 1,不需要bi[b][a] = 1;
    }
    //floyd算法
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(i != j)
            {
                //如果j可以i，则i可以到达的点j都可以到达，所以或一下
                if(bi[j][i])    bi[j] |= bi[i];
            }
        }
    }
    //找出有多少个点没有相连
    //注意第二个循环的其实条件，不然ans会变大
    //对于i到j，只要bi[i][j]和bi[j][i]其中一个是1即可表示两点相连，因为连的是单向边
    for(int i = 1; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            if(!bi[i][j] && !bi[j][i])  ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}