每日一题 day60 打卡
Analysis
这道题一看就感觉是个拓扑排序，但因为按字典序最小的排序会有问题（见第三个样例）主要原因是每次选择有后效性，而从后往前就不会存在这个问题，因为每个子任务都是一个点。
于是就是一个裸的拓扑排序了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define int long long #define maxn 100000+10 #define rep(i,s,e) for(register int i=s;i<=e;++i) #define dwn(i,s,e) for(register int i=s;i>=e;--i) using namespace std; inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} return f*x; } inline void write(int x) { if(x<0) {putchar('-'); x=-x;} if(x>9) write(x/10); putchar(x%10+'0'); } int T; int n,m,cnt,num; int head[maxn],ans[maxn]; int degree[maxn],book[maxn]; struct node { int v,nex; }edge[maxn]; priority_queue<int> q; inline void add(int x,int y) { edge[++cnt].v=y; edge[cnt].nex=head[x]; head[x]=cnt; } signed main() { T=read(); while(T--) { cnt=0; num=0; memset(head,0,sizeof(head)); memset(degree,0,sizeof(degree)); n=read();m=read(); rep(i,1,m) { int x=read(),y=read(); add(y,x); degree[x]++; } rep(i,1,n) if(degree[i]==0) q.push(i); while(!q.empty()) { int top=q.top(); q.pop(); ans[++num]=top; for(int i=head[top];i;i=edge[i].nex) { int to=edge[i].v; --degree[to]; if(degree[to]==0) q.push(to); } } if(num<n) {printf("Impossible! "); continue;} dwn(i,n,1) {write(ans[i]); putchar(' ');} printf(" "); } return 0; }
请各位大佬斧正（反正我不认识斧正是什么意思）