拓扑排序

拓扑排序

要用list，不能用vector，确保删除边的开销为O(1)。

因为主循环中，总共要从队列中pop掉n个数（点），然后总共要删e条边，删点和边的开销都是O(1)。所以整个时间复杂度就是O(n+e)。

如果最终还剩下边，证明存在环，sort失败。

bool sort(list<pair<int, int> > &graph, int n, vector<int> &ans) {
    vector<int> prev(n, 0);
    for (auto it = graph.begin(); it != graph.end(); it++) {
        prev[it->second]++;
    }

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (prev[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int top = q.front();
        q.pop();
        ans.push_back(top);

        for (auto it = graph.begin(); it != graph.end(); ) {
            if (it->first == top) {
                prev[it->second]--;
                if (prev[it->second] == 0) q.push(it->second);
                it = graph.erase(it);
            } else {
                it++;
            }
        }
    }

    return graph.empty();
}