bzoj 4010 [HNOI2015]菜肴制作——贪心

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4010

和 bzoj 2535 差不多。因为当前怎么决策与该点后面连的点的标号情况有关，所以按倒着的拓扑序决策。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=1e5+;

int T,n,m,hd[N],xnt,to[N],nxt[N];

int deg[N],ans[N]; bool vis[N],ins[N],flag;

int dfn[N],low[N],tim;

priority_queue<int> q;

int Mn(int a,int b){return a<b?a:b;}

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;deg[y]++;}

void dfs(int cr)

{

  vis[cr]=ins[cr]=;dfn[cr]=low[cr]=++tim;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]])dfs(v),low[cr]=Mn(low[cr],low[v]);

    else if(ins[v]){flag=;return;}

  ins[cr]=;

}

int main()

{

  T=rdn();

  while(T--)

    {

      n=rdn();m=rdn(); xnt=;flag=;

      memset(hd,,sizeof hd);memset(deg,,sizeof deg);

      for(int i=,u,v;i<=m;i++)

    u=rdn(),v=rdn(),add(v,u);

      memset(vis,,sizeof vis);memset(ins,,sizeof ins);

      tim=;

      for(int i=;i<=n;i++){if(!vis[i])dfs(i);if(flag)break;}

      if(flag){puts("Impossible!");continue;}

      for(int i=;i<=n;i++)if(!deg[i])q.push(i);

      int p0=n;

      while(q.size())

    {

      int k=q.top();q.pop();

      ans[p0--]=k;

      for(int i=hd[k],v;i;i=nxt[i])

        if(!(--deg[v=to[i]]))q.push(v);

    }

      for(int i=;i<=n;i++)printf("%d ",ans[i]);puts("");

    }

  return ;

}