官方题解：因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点条入边都删掉，然后加入拓扑序列。可以证明，，这一定是最优的。具体实现可以用线段树维护每个位置的.#include "stdio.h"#include "string.h"#include "vector"using namespace std;const int inf=0x3f3f3f3f;vector<int>mark[100010];int key,cnt;int du[100010];struct node{int x,l,r;}data[400010];int Min(int a,int b){if (a<b) return a;else return b;}void build(int l,int r,int k){int mid;data[k].l=l;data[k].r=r;if (l==r){data[k].x=du[data[k].l];return;}mid=(l+r)/2;build(l,mid,k*2);build(mid+1,r,k*2+1);data[k].x=Min(data[k*2].x,data[k*2+1].x);}void updata(int x,int k){int mid;if (data[k].l==data[k].r){data[k].x–;return;}mid=(data[k].l+data[k].r)/2;if (x<=mid) updata(x,k*2);else updata(x,k*2+1);data[k].x=Min(data[k*2].x,data[k*2+1].x);}void query(int k){if (data[k].l==data[k].r){cnt-=data[k].x;key=data[k].l;data[k].x=inf;return ;}if (data[k*2+1].x<=cnt)query(k*2+1);elsequery(k*2);data[k].x=Min(data[k*2].x,data[k*2+1].x);}int main(){int n,m,i,a,b,x;while (scanf("%d%d%d",&n,&m,&cnt)!=EOF){memset(du,0,sizeof(du));for (i=1;i<=m;i++){scanf("%d%d",&a,&b);mark[a].push_back(b);du[b]++;}build(1,n,1);for (a=1;a<=n;a++){query(1);if (a==1)printf("%d",key);elseprintf(" %d",key);for (i=0;i<mark[key].size();i++){x=mark[key][i];updata(x,1);}}printf("\n");}return 0;}
而开始追寻他内心世界的真正财富
