644. 课程安排问题
★ 输入文件：curriculum.in 输出文件：curriculum.out 简单对比
时间限制：1 s 内存限制：128 MB
问题描述
一个软件专业的学生必须学习一系列基本课程，其中有些课程是基础课，它独立于其它课程，如《高等数学》、《计算引论》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如，在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先（优先）关系。请你在符合上述领先（优先）条件的前提下，给出所有课程的一个有序序列，以方便学校排课。
【输入格式】
输入文件有若干行
第一行，一个整数n，表示共有n(0<n<=100)门课程
第2--n+1行分别表示第1--n门课程的先修课程信息，每行有若干个整数m,s1,s2,...,sm
m表示该门课程有m门先修课程，s1,s2,...,sm分别表示m门先修课的编号，如果该门课没有先修课程，则m为0。
第一行，一个整数n，表示共有n(0<n<=100)门课程
第2--n+1行分别表示第1--n门课程的先修课程信息，每行有若干个整数m,s1,s2,...,sm
m表示该门课程有m门先修课程，s1,s2,...,sm分别表示m门先修课的编号，如果该门课没有先修课程，则m为0。
【输出格式】
一行，n个整数，表示n门课程编号的有序序列(如果这样的序列不存在，则输出no;如果有多个这样的序列，输出字典序最小的)
【输入输出样例】
输入文件名： curriculum.in
4
0
1 1
1 1
2 2 3
0
1 1
1 1
2 2 3
输出文件名：curriculum.out
1 2 3 4
思路：
拓扑排序，进队时使用优先队列、、（保证字典序最小）
代码；
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 2000
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int x,s,tot,n,m,sum,ans[N],in[N],head[N];
int read()
{
,f=; char ch=getchar();
; ch=getchar();}
+ch-'; ch=getchar();}
return x*f;
}
struct Edge
{
int from,to,next;
}edge[N];
int add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
int main()
{
freopen("curriculum.in","r",stdin);
freopen("curriculum.out","w",stdout);
n=read();
;i<=n;i++)
{
m=read();
;j<=m;j++)
x=read(),add(x,i),in[i]++;
}
;i<=n;i++)
) q.push(i);
while(!q.empty())
{
x=q.top(),q.pop();
sum++;ans[++s]=x;
for(int i=head[x];i;i=edge[i].next)
{
int t=edge[i].to;
in[t]--;
) q.push(t);
}
}
if(sum!=n) printf("no\n");
else
{
;i<=s;i++)
printf("%d ",ans[i]);
}
;
}