有序图

#include <bits/stdc++.h>
using namespace std;

const int M = 100003;
vector<int> E[M];
int indegree[M];

int main(){
    int n, m, u, v;
    cin>>n>>m;
    int r[n+1];
    for(int i=0;i<m;i++){
        cin>>u>>v;
        E[v].push_back(u);
        indegree[u]++;
    }
    priority_queue<int> q;
    for(int i=1;i<=n;i++)
        if(!indegree[i])
            q.push(i);
    int k = n;
    while(!q.empty()){
        int p = q.top();
        q.pop();
        r[p] = k--;
        for(int i=0;i<E[p].size();i++){
            v = E[p][i];
            indegree[v]--;
            if(indegree[v]==0)
                q.push(v);
        }
    }
    for(int i=1;i<=n;i++){
        if(i==n)
            cout<<r[i]<<endl;
        else
            cout<<r[i]<<" ";
    }
    return 0;
}

#include <bits/stdc++.h>

//freopen("temp.in","r",stdin);(1522)#include "utils.cpp"
using namespace std;

#define UF(i,start,end) for(auto i=start;i<end;i++)
(1523)#define DF(i,start,end) for(auto i=start;i>=end;i--)
int ri(){int a;scanf("%d",&a);return a;}//读取整数并返回
string rs(){string s;cin>>s;return s;}
typedef long long ll;
typedef vector<int> veci;
typedef vector<bool> vecb;
typedef vector<string> vecs;
typedef vector<vector<int>> vveci;

veci split(string s,char c){
    veci V;
    int i=0,j=1,n=s.length();
    while(i<n){
        while(j<n and s[j]!=c) j++;
        if(j==n-1) j++;
        V.push_back(atoi(s.substr(i,j-i).c_str()));
        i=j+1;
        j++;
    }
    return V;
}

template<typename T> ostream& operator<<(ostream& os,const vector<T>& v){
	for(auto t:v)
		os<<t<<" ";
	os<<endl;
	return os;
}
template <typename T>
ostream &print(ostream &os,const T &t){
	return os<<t<<endl;
}	
template <typename T,typename... Args>
ostream &print(ostream &os,const T &t,const Args&... rest){
	os << t <<" ";
	return print(os,rest...);
}	
template <typename T,typename... Args>
void PR(const T &t,const Args&... rest){
	print(cout,t,rest...);
}
template <typename T>
void reverse(T &t){
    reverse(t.begin(),t.end());
}
struct BigInteger{
    veci data;
    int size;
    BigInteger():size(0){}
    BigInteger(int val){
        size = 0;
        while(val){
            size++;
            data.push_back(val%10);
            val/=10;
        }
    }
   void multiply(BigInteger b){
        veci T(size,0);
        int temp = size;
        UF(i,0,b.size){
            UF(j,0,temp){
                if(j+i>=size){
                    size++;
                    T.push_back(data[j]*b.data[i]);
                }else
                    T[j+i]+=data[j]*b.data[i];
                 
             
            }
        }
         
        temp = size;
        UF(i,0,temp){
            if(T[i]>9){
                if(i==temp-1){
                    size++;
                    T.push_back(T[i]/10);
                }else T[i+1]+=T[i]/10;
                T[i]%=10;
            }
        }
        data.assign(T.begin(),T.end());
    }
    void print(){
        DF(i,size-1,0){
            cout<<data[i];
        }
        cout<<endl;
    }
    
};
 int random(int k){
	   return rand()%k+1;
   }
	vector<int> create_data(){
		PR(random(10),random(20));
	}
	
	void test(){
		unsigned seed = time(0);
		srand(seed);
		freopen("temp.out", "w", stdout);
		int N=5;//生成测试数据组数
		for(int i=0;i<N;i++)
			create_data();
	}
	
//拓扑
int MAX_N=100000;
vveci G(MAX_N);
int main(){
	//freopen("temp.in","r",stdin);
	//test();
    int n,m;
    cin>>n>>m;//写成模板输入
    int u,v;

/*
    拓扑排序+优先级队列
    参考了别人的代码才理解
    题目要求最小字典序，则要从后往前排没有出度的节点，为什么不从前往后呢，因为前
面的节点会受指向它的节点的排序影响 10 10 9 7 5 2 10 2 5 8 1 2 10 7 3 2 4 2 8 7 1 8 对应输出应该为: 1 6 2 3 4 7 10 8 9 5   */
    veci C(n+1,0);//出度
    
    priority_queue<int,vector<int>,less<int> > Q;//大的优先 从大到小出队列
    UF(i,0,m){
        cin>>u>>v;
        G[v].push_back(u);//G[v]  指向v的边 而不是v指向别人
        C[u]+=1;//从u点出的边个数
    }
    veci ans(n+1);
    int k=0;
    UF(i,1,n+1){
        if(C[i]==0) Q.push(i);//将出度为0的点入队列
    }
    int cnt=n;
    while(cnt>0){
        auto a=Q.top();
        Q.pop();
        ans[a]=cnt--;//让编号较小节点的保留更大的编号，先让后面编号大的又没有输出的点先排序
        for(auto b:G[a]){//将指向自身的边的出度-1
            C[b]--;
            if(C[b]==0){
                Q.push(b);//没有出度时入队列
            }
        }
        
    }
    UF(i,1,n)
        cout<<ans[i]<<" ";
    cout<<ans[n]<<endl;
	return 0;
	
}