7-2 任务拓扑排序
一个工程被分解成n个子任务，编号为0至n-1。要完成整个工程需要完成所有的子任务。其中一些子任务必须先于另外一些子任务被完成。给定各子任务之间的先后关系，请编写程序给出一个合理的任务完成顺序，若工程不可行，程序亦能识别。
输入格式:
输入第一行为两个整数n和e，均不超过100。n表示子任务数。接下来e行，表示已知的两个子任务间的先后关系，每行为两个整数a和b，表示任务a必须先于任务b完成。
输出格式:
若工程不可行（一些子任务以自己为先决条件），输出“unworkable project”；若工程可行，输出为1行整数，每个整数后一个空格，为n个子任务的编号，表示子任务的完成顺序，如果有多种可能的顺序，则输出字典序最小者。
注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。
输入样例1:
3 2
0 1
1 2
输出样例1:
0 1 2
输入样例2:
3 3
0 1
1 2
2 0
输出样例2:
unworkable project
评测详情
测试点 内存(KB) 用时(ms) 结果 得分
0 444 6 答案错误 0/6
样例都能过，就测试点过不去，有没有大神教一下。
#include <iostream>
#include <stdio.h>
#include <cstdlib>
using namespace std;
#define MVNum 101
#define OK 1
#define ERROR 0
typedef struct Edge
{
int end;
struct Edge *next;
}Edge;
Edge *head[MVNum];
int degree[MVNum];
int Q[MVNum];
int top[MVNum];
int vexnum,arcnum;
void init()
{
for(int i=0;i<vexnum;i++)
head[i]=NULL;
}
int tpsort()
{
int i,v,k=0;
int front=0,rear=0;
Edge *p;
for(i=0;i<vexnum;i++)
{
if(degree[i]==0)
Q[rear++]=i;
}
while(front<rear)
{
v=Q[front++];
k++;
for(p=head[v];p!=NULL;p=p->next)
{
degree[p->end]--;
if(degree[p->end]==0)
{
Q[rear++]=p->end;
}
}
}
if(k==vexnum)
return OK;
return ERROR;
}
int sort(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int main()
{
int i,v1,v2;
cin>>vexnum>>arcnum;
for(i=0;i<arcnum;i++)
{
cin>>v1>>v2;
degree[v2]++;
Edge *p=new Edge;
p->end=v2;
p->next=head[v1];
head[v1]=p;
}
if(tpsort())
{
qsort(Q,vexnum,sizeof(int),sort);
for(i=0;i<vexnum;i++)
cout<<Q[i]<<" ";
}
else cout<<"unworkable project";
return 0;
}
