A - 小Y上学记——修学分
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Problem Description
小Y终于如愿以偿地通过高考来到了魂牵梦萦的大学校园——ACdream大学。来到校园的第一件事就是选课。
由于每一门课都有1个学分~而且有一些课需要先学完别的课程（例如必须先学会高等数学，才能学会量子力学，必须先学会走，才能学会跑）
ACdream大学需要学生修够若干学分才允许毕业。
请按顺序输出小Y的一种方案（若不止一种答案，请输出字典序最小的一种方案)
Input
多组数据，每组数据首先是两个整数n,m,k,分别表示学科总数，学科之间的关系数，以及毕业所需的最少学分。
(2<=n<=100, 0<=m<=500,1<=k<=n)
接下来是m行，每行是两个整数a,b表示学科a是学科b的前置学科。
Output
对于每组数据，若小Y不存在任何方案选课，请输出-1.
否则在一行输出m个整数，表示小Y按顺序修的学科编号。
Sample Input
2 1 2
0 1
2 2 2
1 0
0 1
3 2 1
1 0
0 1
3 0 3
Sample Output
0 1
-1
2
0 1 2
Hint
对于第一组数据，先修完第0学科，获得1学分，再修以第0学科为前置学科的第1学科，获得1学分，即可满足毕业条件：2学分。
对于第二组数据，由于第0学科的前置学科为第1学科，而第1学科的前置学科为第2学科，因此小Y无论如何也无法满足毕业条件。
对于第三组数据，由于多了第2学科，而且第2学科不需要前置学科，因此只需要修完第2学科即可满足毕业条件了。
对于第四组数据，没有任何的先后限制，因此6种全排列方案均符合题意，字典序最小的方案为0,1,2
解法：ToPoSort一下，排序K个即可。
代码：2015.7.30
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#define MAX 505
using namespace std;
int InD[];/*InD[i]记录点i的入度*/
int First[MAX];/*First[i]头结点的第一条边的编号*/
struct edge
{
int TO;/*点*/
int Next;/*下一条边的编号*/
}ID[*MAX];
int SIGN;
void Add_E(int x,int y)/*添加点操作*/
{
ID[SIGN].TO=y;
InD[y]++;
ID[SIGN].Next=First[x];
First[x]=SIGN++;
}
int Jude(int x,int y)/*查找与X是否与Y相连*/
{
int i;
for(i=First[x];i!=;i=ID[i].Next) //查找与该点相关的点
{
if(ID[i].TO==y)return ;
}
return ;
}
int ToPoSort(int N,int Num[],int K)/*拓扑排序，邻接表*/
{
int i,j,k;
for(j=;j<N;j++)
{
for(i=;i<=N;i++)
{
if(InD[i]==)
{
InD[i]--;
Num[j]=i;
for(k=First[i];k!=;k=ID[k].Next)
{
InD[ID[k].TO]--;
}
break;
}
}
if(i>N)break;
}
if(j>=K)return ;
else return ;
}
int main()
{
int M,N,K,i;
int a,b;
int Num[MAX];
while(scanf("%d%d%d",&N,&M,&K)!=EOF)
{
for(i=;i<=N;i++){First[i]=;InD[i]=;}
for(i=,SIGN=;i<M;i++)
{
scanf("%d%d",&a,&b);a+=;b+=;
Add_E(a,b);
}
if(ToPoSort(N,Num,K))/*拓扑排序*/
{
for(i=;i<K;i++)
{
if(i!=)putchar();
printf("%d",Num[i]-);
}putchar();
}
else printf("-1\n");
}
return ;
}