ACM UVA 10305 (Ordering Tasks)

题目： 

思路： (简单的拓扑排序)

代码：

//
// UVA 10305
// topsort
//
// Author: xfye
// Status: AC
//

#include <iostream>
#include <vector>
#include <list>

using namespace std;

struct Task
{
    Task()
    {
        id = 0;
        numPreTasks = 0;
    }
    int id;
    int numPreTasks;
    vector<Task*> followingTasks;
};

int main()
{
    int n, m;

    cin >> n >> m;
    while (n != 0) {
        Task tasks[101];
        for (int i = 1; i <= n; i++) {
            tasks[i].id = i;
        }
        for (int i = 0; i < m; i++) {
            int t1, t2;
            cin >> t1 >> t2;
            tasks[t2].numPreTasks++;
            tasks[t1].followingTasks.push_back(&tasks[t2]);
        }

        list<Task*> leftTasks;
        for (int i = 1; i <= n; i++) {
            if (tasks[i].numPreTasks == 0) {
                leftTasks.push_back(&tasks[i]);
            }
        }

        //
        // topsort
        //
        int first = true;
        while (leftTasks.size() > 0) {
            Task *tsk = leftTasks.front();
            if (tsk->numPreTasks == 0) {
                if (!first) {
                    cout << " ";
                } else {
                    first = false;
                }
                cout << tsk->id;
                for (int i = 0; i < tsk->followingTasks.size(); i++) {
                    tsk->followingTasks[i]->numPreTasks--;
                    if (tsk->followingTasks[i]->numPreTasks == 0) {
                        leftTasks.push_back(tsk->followingTasks[i]);
                    }
                }
                leftTasks.remove(tsk);
            }
        }
        cout << endl;

        cin >> n >> m;
    }
}