学步园

好吧，是拓扑排序，我一开始直接想成快排了，一直wa

快排其实很方便，他能够按照任意两个元素确定前后顺序，得到任意两个都符合这些大小关系的序列

那为什么wa呢。其实很简单，我没去细想，还是铠甲师兄提出来才焕然大悟，

我们确定了两个数的直接关系，那么间接关系呢？也是一定要满足的吧，快排可不管你中间会有多少种直接关系来构成间接关系

例如 1 2 2 3如果快排直接遇到了1 3 ，他们的关系是不确定的，就会出错

他只会直接判断，所以我们要确定下来，先用暴力求出来他们所有的间接关系，就可以ac了。怎么求呢。就是类floyd的dp，

所以以后用快排里面的元素的顺序一定要确定下来，包括相对顺序

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=100+10;
int pj[MAXN][MAXN];
int n,m;
vector<int> a;
int cmp(int a,int b)
{
    return pj[a][b];
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0 && m==0) break;
        a.clear();
        memset(pj,0,sizeof(pj));
        for(int i=0;i<n;i++) a.push_back(i);
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            u--,v--;
            pj[u][v]=true;
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    pj[i][j]|=pj[i][k]&pj[k][j];
        sort(a.begin(),a.end(),cmp);
        for(int i=0;i<n;i++)
        {
            if(i) putchar(' ');
            printf("%d",a[i]+1);
        }
        putchar(10);
    }

    return 0;
}