时间限制：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门课程编号的有序序列(如果这样的序列不存在，则输出no;如果有多个这样的序列，输出字典序最小的)
【输入输出样例】
输入文件名： curriculum.in
4 0 1 1 1 1 2 2 3
输出文件名：curriculum.out
1 2 3 4 【分析】 这应该也算是经典习题了吧。。这里就当是恢复状态→_→首先这是个很明显的topo sort，但由于题目丧心病狂地要求最小字典序，这里不得不把算导上介绍的DFS换成基于最小堆的层次遍历算法……OMG，堆的代码之前已经练过了，那么这里就用STL水过去吧。
1 #include <cstdio> 2 #include <fstream> 3 #include <queue> // priority_heap 4 #include <vector> 5 #include <functional> // use of FUNCTOR "greater<int>" 6 using namespace std; 7 ifstream in( " curriculum.in "); 8 ofstream out( " curriculum.out "); 9 bool settled[ 102]={ 0}; 10 int M[ 102]={ 0}; 11 int N; 12 int ans[ 102], last = 0; 13 vector < int> Next[ 102]; 14 priority_queue < int, vector< int>, greater< int> >Q; 15 void init() 16 { 17 int i, j, k; 18 for(i = 1;i <=N; ++i) 19 { 20 in >> M[i]; 21 if(!M[i]) // Roots 22 Q.push(i); 23 else for(j = 0;j < M[i];++j) 24 { 25 in >> k; 26 Next[k].push_back(i); 27 } 28 } 29 } 30 void Topo() 31 { 32 int k; 33 vector < int>::iterator it; 34 while(!Q.empty()) 35 { 36 k = Q.top();Q.pop(); 37 ans[last++] = k; 38 settled[k] = 1; 39 for(it = Next[k].begin();it!=Next[k].end();++it) 40 { 41 if(!settled[*it]) 42 { 43 M[*it]--; 44 if(!M[*it])Q.push(*it); 45 } 46 else return; // ring 47 } 48 } 49 } 50 int main() 51 { 52 int i; 53 ios::sync_with_stdio( 0); 54 in >> N; 55 init(); 56 Topo(); 57 if(last != N) 58 out << " no "; 59 else for(i = 0;i < N; ++i) 60 out << ans[i] << ' '; 61 return 0; 62 }