内江移动网站建设,网站内部链接的作用有哪些,企业网站开发实训报告,网站使用功能介绍是用什么软件做的正题
题目链接:https://www.luogu.com.cn/problem/P3243 题目大意 nnn个数#xff0c;有mmm个要求形如xxx在yyy的前面#xff0c;现在要求在i−1i-1i−1尽量靠前的情况下iii尽量靠前(i1)(i1)(i1) 求这个序列 解题思路
这个很显然要求是张有向图无环图#xff…正题
题目链接:https://www.luogu.com.cn/problem/P3243 题目大意
nnn个数有mmm个要求形如xxx在yyy的前面现在要求在i−1i-1i−1尽量靠前的情况下iii尽量靠前(i1)(i1)(i1) 求这个序列 解题思路
这个很显然要求是张有向图无环图然后若第iii个数排在第xxx位那么pixp_ixpix那么就是要求ppp的字典序最小。但是发现如果直接拓扑排序优先队列就会导致拓扑序的字典序最小不符合题意但是如果我们将拓扑图反过来跑就是正确答案了。
这样子跑是保证了反过来的字典序最大那么小的一定在后面也就是保证了反过来后pip_ipi小的一定在前面。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N];
int T,n,m,tot,cnt,in[N],ls[N],top[N];
priority_queueint q;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;in[y];return;
}
void topsort(){for(int i1;in;i)if(!in[i])q.push(i);while(!q.empty()){int xq.top();top[cnt]x;q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;in[y]--;if(!in[y])q.push(y);}}return;
}
int main()
{scanf(%d,T);while(T--){totcnt0;memset(ls,0,sizeof(ls));memset(in,0,sizeof(in));scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(y,x);}topsort();if(cnt!n)printf(Impossible!);else{for(int in;i1;i--)printf(%d ,top[i]);}putchar(\n);}return 0;
}
