三种方法类似，记录数据和删除以没有前驱的顶点为尾的箭头时有点区别

1 /*hdu1285--采用二维数组记录两者之间的关系*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 int map[510][510];//前驱数量  7 int indegree[510]; 8 int queue[510];//保存拓扑序列  9 void topo(int n)10 {11     int i,j,m,t=0;12     for(j=1;j<=n;j++){13         for(i=1;i<=n;i++){14             if(indegree[i]==0){
   //找出前驱数量为零的的点即每次找到第一名 15                 m=i;break;16             }17         }18         queue[t++]=m;indegree[m]=-1;//将第一名的前驱数量设为-1 19         for(i=1;i<=n;++i){
   //第二步将前驱中含有第一名的点前驱数量减1 20             if(map[m][i])indegree[i]--;21         }22     }23     printf("%d",queue[0]);//输出拓扑序列 24     for(i=1;i
       
      
     

1 /*hdu1285--采用邻接表记录两者之间的关系*/  2 #include
     
       3 #include
      
        4 int head[510]; 5 int indegree[510]; 6 int queue[510]; 7 int num; 8 struct stu{ 9    int to,next;10 }edge[2510];11 void inin(){
   //初始化 12     memset(indegree,0,sizeof(indegree)); 13     memset(head,-1,sizeof(head));14     num=0;15 }16 void add(int a,int b){
   //添加边 17    stu E={b,head[a]};18    edge[num]=E;19    head[a]=num++;20    indegree[b]++;21 }22 void topo(int n){23     int i,j,id,t=0;24     for(j=1;j<=n;j++){25         for(i=1;i<=n;i++){26             if(indegree[i]==0){27               id=i;28               break;    29             }30         }31         queue[t++]=id;indegree[id]=-1;32         for(i=head[id];i!=-1;i=edge[i].next){33             int k=edge[i].to;34             indegree[k]--;35         }36     }37     printf("%d",queue[0]);//输出拓扑序列 38     for(i=1;i
      
     

1 /*hdu1285--采用队列记录两者之间的关系*/  2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include 
         
            7 using namespace std; 8 int map[510][510]; 9 int indegree[510]; 10 void topo(int n)11 {12     int i,j,m,t=0;13     priority_queue
          
           
            ,greater
            
              >Q;//按从小到大顺序输出队14 for(i=1;i<=n;i++){15 if(indegree[i]==0){16 Q.push(i);17 }18 }19 int sign=1;20 while(!Q.empty()){21 int top=Q.top();22 Q.pop();23 indegree[top]=-1;24 if(sign)25 printf("%d",top);26 else27 printf(" %d",top);28 sign=0;29 for(i=1;i<=n;i++){30 if(map[top][i]){31 indegree[i]--;32 if(indegree[i]==0){33 Q.push(i);34 }35 }36 }37 }38 printf("\n");39 }40 int main()41 {42 int n,m,i,j,a,b;43 while(scanf("%d%d",&n,&m)!=EOF){44 memset(indegree,0,sizeof(indegree));45 memset(map,0,sizeof(map));46 for(i=0;i