拓扑排序 HDU - 1285 【Topological sort】

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

思路：Toposort，每次找度==0。题目要求编号小的在前并用小顶堆

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 500+5;

vector <int> edge[MAX_N];
int indegree[MAX_N];

void init() {

    for (int i = 1;i < MAX_N; ++i)indegree[i] = 0,edge[i].clear();
}

int main()
{
    int n, m;
    while (cin >> n >> m) {
        init();
        for (int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            edge[u].push_back(v);
            ++indegree[v];
        }
        vector <int> res;
        //queue<int> temp;
        priority_queue<int, vector<int>, greater<int> >temp;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                temp.push(i);
            }
        }

        while (temp.size() > 0) {
            int v = temp.top(); temp.pop();
            res.push_back(v);
            for (auto p : edge[v]) {
                if (--indegree[p] == 0) {
                    temp.push(p);
                }
            }
        }
        for (int i = 0; i < res.size(); i++)
        {
            if (i != res.size() - 1)    printf("%d ", res[i]);
            else    printf("%d\n", res[i]);
        }
    }


    return 0;
}