首页 > 代码库 > Uva 10305 Ordering Tasks

Uva 10305 Ordering Tasks

题目为简单的拓扑排序。

第一行输入n,m。n为数字的数目,m为下边有几行数字(i,j)之间的关系。

数字间的关系,j要排在i的后边。最终排成一个序列。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 queue<int>task; 7 int indegree[102],Map[102][102]; 8 void topo(int taskNum){ 9     int outNum;10     for(int i = 1;i <= taskNum;i++){11         if(indegree[i] == 0){12             task.push(i);13         }14     }15     while(!task.empty()){16         outNum = task.front();17         printf("%d",outNum);18         task.pop();19         for(int i = 1;i <= taskNum;i++){//遍历从outNum出发的每一条边,入度减120             if(Map[outNum][i] != 0){21                 indegree[i]--;22                 if(indegree[i] == 0)task.push(i);23             }24         }25         if(!task.empty())cout<<" ";26     }27     cout<<endl;28 }29 int main()30 {31     #ifndef ONLINE_JUDGE32     freopen("d:\\acm.txt","r",stdin);33     #endif // ONLINE_JUDGE34     int taskNum,relation;35     while(cin>>taskNum>>relation,taskNum||relation){36 37         memset(Map,0,sizeof(Map));38         memset(indegree,0,sizeof(indegree));39         for(int j = 0;j < relation;j++){40             int x,y;41             cin>>x>>y;42             Map[x][y] = 1;43             indegree[y] ++;44         }45         topo(taskNum);46     }47     return 0;48 }

 总结:代码写的不够清晰,容易产生bug

Uva 10305 Ordering Tasks