UVA 10305 Ordering Tasks（算法竞赛入门经典，拓扑排序，裸题）

算法竞赛入门经典167页，拓扑排序，裸题

本题要点：
1、用 deg[x], 存放点x的入度。先把所有入度为0 的点加入队列 queue;
2、每次从队头取出一个点 y， 将y 所指向的所有点的入度减去1. 如果某点度数为0， 把该点也加入队列。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 110, MaxM = 10010;
int n, m, tot;
int deg[MaxN], head[MaxN], ver[MaxM], Next[MaxM];void add(int x, int y)
{
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}void solve()
{
    int cnt = 0;queue<int> q;for(int i = 1; i <= n; ++i){
    if(!deg[i])q.push(i);}while(q.size()){
    int x = q.front();q.pop();printf("%d", x);if(++cnt == n)printf("\n");else{
    printf(" ");}for(int i = head[x]; i; i = Next[i]){
    int y = ver[i];deg[y]--;if(deg[y] == 0){
    q.push(y);}}}
}int main()
{
    int x, y;while(scanf("%d%d", &n, &m) != EOF){
    if(0 == n && 0 == m)break;memset(deg, 0, sizeof deg);memset(head, 0, sizeof head);for(int i = 0; i < m; ++i){
    scanf("%d%d", &x, &y);deg[y]++;add(x, y);}solve();}return 0;
}/* 5 4 1 2 2 3 1 3 1 5 0 0 *//* 1 4 2 5 3 */