题目描述：

一个人想给n个东西排序，已经知道m个关系。每个关系用a，b表示a大于b。

问他最少还需要多少个关系能把这n个东西排序。

解题报告：

排序的话，一共会有n * (n – 1) / 2个关系。只要知道当前的m个关系一共能确定多少关系（sum个），拿n * (n – 1) / 2减去sum就是答案。

Folyd即可，k，i，j，relation[i][j] = relation[i][j] || relation[i][k] && relation[k][j]。

这样就可以得到m个关系确定的所有关系。

注意可以优化：每一个数的出点和入点可以用邻接表vector存

for(int k = 1; k <= n; k++)

    for(int i = 0; i < in[k].size(); i++)

        for(int j = 0; j < out[k].size(); j++)

这样的。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define SIZE 1001
int n, m, a, b;
bool g[SIZE][SIZE];
vector<int> out[SIZE], in[SIZE];
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        while(m-- && scanf("%d%d", &a, &b)) out[a].push_back(b), in[b].push_back(a), g[a][b] = 1;
        int sum = 0;
        for(int k = 1; k <= n; k++)
            for(int i = 0; i < in[k].size(); i++)
                for(int j = 0; j < out[k].size(); j++)
                    if (!g[in[k][i]][out[k][j]] && g[in[k][i]][k] && g[k][out[k][j]])
                    {
                        g[in[k][i]][out[k][j]] = 1;
                        in[out[k][j]].push_back(in[k][i]);
                        out[in[k][i]].push_back(out[k][j]);
                    }
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) sum += g[i][j];
        printf("%d\n", (n * (n - 1) >> 1) - sum);
    }
    return 0;
}