拓扑排序 Topological Order

总时间限制: 1000ms  内存限制: 65536kB

给出一个图的结构，输出其拓扑排序序列，要求在同等条件下，编号小的顶点在前。

若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有2个数，分别是该条弧所关联的两个顶点编号。
v<=100, a<=500

若干个空格隔开的顶点构成的序列(用小写字母)。

6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5

v1 v3 v2 v6 v4 v5

1. 怎样寻找拓扑排序中的下一个结点？没有父结点的结点都可以作为下一个结点
2. 本题要求输出字典序最小的拓扑排序，那么只要用堆维护下一个结点的所有候选者即可
3. 每次从堆中选取一个结点，然后删除所有和这个结点相关的边。其实这个结点只有出边，需要删除的是其子结点的入边记录，否则程序会判断这些子结点会一直有父结点，就不能按1中的规则选出来了！

#include 
#include 
#include 
#include 
using namespace std;

const int V = 105;
vector front[V];
vector back[V];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int v = 0, a = 0;
    scanf("%d%d", &v, &a);
    while (a--) {
        int v1 = 0, v2 = 0;
        scanf("%d%d", &v1, &v2);
        front[v2].push_back(v1);
        back[v1].push_back(v2);
    }

    priority_queue, greater> next;
    for (int i = 1; i <= v; ++i) {
        if (front[i].empty()) {
            next.push(i);
        }
    }

    while (!next.empty()) {
        int curr = next.top();
        next.pop();
        printf("v%d ", curr);
        for (auto i = back[curr].begin(); i != back[curr].end(); ++i) {
            auto iter = find(front[*i].begin(), front[*i].end(), curr);
            front[*i].erase(iter);
            if (front[*i].empty()) {
                next.push(*i);
            }
        }
    }
    return 0;
}