拓撲排序
這題是拓樸排序,但是要注意題目要求依照字典序最小輸出。
其實只要將原本的queue,換成priority_queue就可以了。
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define N 100001
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int D[N],ST[N],st;
int main(int argc,char *argv[])
{
ios_base::sync_with_stdio(false);
int n,m,a,b;
cin>>n;
while(cin>>n>>m){
memset(D,0,sizeof(D));
st=0;
vector<int> M[N];
F(m){
cin>>a>>b;
M[a].push_back(b);
D[b]++;
}
priority_queue<int>qq;
F(n)if(D[i]==0)qq.push(-i);
while(!qq.empty()){
int now=-qq.top();
qq.pop();
ST[st++]=now;
F(M[now].size())
if(--D[M[now][i]]==0)qq.push(-M[now][i]);
}
if(st==n){
cout<<ST[0];
F(n-1)cout<<' '<<ST[i+1];
}
else cout<<"QAQ";
cout<<endl;
}
return 0;
}
沒有留言:
張貼留言