http://acm.hdu.edu.cn/showproblem.php?pid=1285

拓扑排序：次序问题

AOV网：

用顶点表示活动，弧表示活动间的优先关系的有向图，AOV网中不应该出现有向环：

如果存在环，则某项活动以自己为先决条件。

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 int n,m; 5 int map[501][501],d[501],v[501]; 6 int main() 7 { 8     int x,y; 9     int flag;10     while(scanf("%d%d",&n,&m)!=EOF)11     {12         memset(v,0,sizeof(v));13         memset(d,0,sizeof(d));14         memset(map,0,sizeof(map));15         while(m--)16         {17             scanf("%d%d",&x,&y);18             if(!map[x][y])19             {20                 map[x][y]=1;21                 d[y]++;22             }23         }24         flag=0;25         for(int i=1;i<=n;i++)26         {27             for(int j=1;j<=n;j++)28             {29                 if(v[j]==0&&d[j]==0)30                 {31                     for(int k=1;k<=n;k++)32                         if(map[j][k])33                           d[k]--;34                     v[j]=1;35                     if(flag==0)36                     {37                          printf("%d",j);38                          flag=1;39                     }40                     else printf(" %d",j);41                     break;42                 }43             }44         }45         printf("\n");46 47     }48     return 0;49 }