我要讲的其实是下面这道题：

对于n个数，一直它们间m对关系（即pi>pj），问至少还需要知道多少堆关系才能将它们排序。

问题理解起来很简单，相信有的读者一眼看去就知道是拓扑排序(我一开始也是这么认为的），那么我就仅仅附上拓扑排序的代码，因为我真正要讲的，并不是拓扑排序法

#include
     
      using namespace std;const int maxn=1000+15;int n,m,sum;int head[maxn],vis[maxn];bitset
      
        rel[maxn];struct EDGE{    int to;int next;}edge[maxn*20];void add(int x,int y){    edge[++sum].next=head[x];    edge[sum].to=y;    head[x]=sum;}void dfs(int x){    vis[x]=1;    for (int i=head[x];i;i=edge[i].next)    {    if (!vis[edge[i].to]) dfs(edge[i].to);        rel[x]|=rel[edge[i].to];    }}int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++)    rel[i][i]=true;    for (int i=1;i<=m;i++)    {        int u,v;        scanf("%d%d",&u,&v);        add(u,v);    }    for (int i=1;i<=n;i++)    if (!vis[i]) dfs(i);    int ans=0;    for (int i=1;i<=n;i++) ans+=rel[i].count();    printf("%d",n*(n-1)/2-ans+n);    return 0; }
      
     

 

之所以不讲，是因为我认为我还不能完全的理解

下面我来介绍一种更为简单的方法（floyd）

首先告诉大家这题的数据，n<=1000,那么正常情况下n^3的floyd肯定是不行的了，有个操作叫做手动压位能降低复杂度，然而我不会。我会的方法并不是手动的，而是利用STL库里的bitset进行优化

应该有不少的人不知道bitset是何物，我推荐一个我自己发现的一篇博客，希望对大家有帮助

利用已知关系，我们得到了一张有向无环图，对于任两点i j,若是i能够到j，这对于一个j能到的点集，i都能到达点集中的任意一点(联通）。可以明确，如果给定的关系为0，排序之后我们知道的关系就是n(n-1)/2（对于任意互异两点都知道关系），那么在floyd中我们能够计算出已知关系的数量，从而最终确定答案。下面我附上代码，注意当你看不懂输出的时候，代码下面我还会给予讲解（当然自己想想也不错），上面拓扑排序的代码输出也是一样的。

#include
     
      using namespace std;const int maxn=1000+15;int n,m;bitset
      
       rel[maxn];int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++)    rel[i][i]=true;    for (int i=1;i<=m;i++)    {        int u,v;        scanf("%d%d",&u,&v);        rel[u][v]=true;    }    for (int i=1;i<=n;i++)    for (int j=1;j<=n;j++)    if (rel[j][i]) rel[j]|=rel[i];//注意是判断rel[j][i]，而不是rel[i][j]（循环好像不能反过来写）     int ans=0;    for (int i=1;i<=n;i++)    ans+=rel[i].count();    printf("%d",n*(n-1)/2-ans+n);    return 0; }
      
     

输出讲解：注意一开始我们对所有的i,都有bitset[i][i]=true,因此我们最后要给已知的关系数ans减去n，之后再计算