拓扑排序(推荐)——Reward

By | 2012/08/16

code：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 10010
struct node
{
int k;
struct node *next;
}*map;
int *degree,*money,n;
int maxx(int x,int y)
{
return x>y?x:y;
}
void init()
{
int i;
degree=(int *)malloc(sizeof(int)*(n+1));
money=(int *)malloc(sizeof(int)*(n+1));
map=(struct node *)malloc(sizeof(struct node)*(n+1));
for(i=1;i<=n;i++)
{
map[i].k=0;
map[i].next=NULL;
money[i]=888;
degree[i]=0;
}
}
{
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
degree[x]++;
p->k=x;
p->next=map[y].next;
map[y].next=p;
}
int Topsort()
{
int i,j;
struct node *p;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(degree[j]==0)
{
degree[j]=-1;
break;
}
}
if(j>n)
return 0;
p=map[j].next;
while(p)
{
degree[p->k]–;
money[p->k]=maxx(money[p->k],money[j]+1);
p=p->next;
}
}
return 1;
}
int main()
{
int m,x,y,flag;
while(scanf(“%d%d”,&n,&m)!=EOF)
{
init();
while(m–)
{
scanf(“%d%d”,&x,&y);
}
flag=Topsort();
if(flag)
{
for(m=2;m<=n;m++)
money[1]+=money[m];
printf(“%d\n”,money[1]);
}
else
{
printf(“-1\n”);
}
free(degree);
free(money);
free(map);
}
return 0;
}