算法期中之拓补排序

Problems：

在图论中，拓扑序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列. 且该序列必须满足下面两个条件：

对于一个含有n个节点的有向无环图（节点编号0到n-1），输出它的一个拓扑序.

图的节点数和边数均不多于100000，保证输入的图是一个无环图.

请为下面的Solution类实现解决上述问题的topologicalSort函数，函数参数中n为图的节点数，edges是边集，edges[i]表示第i条边从edges[i].first指向edges[i].second. 函数返回值为有向图的一个拓扑序. 有向图有多个拓扑序时，输出任意一个即可.

class Solution {
public:
vector topologicalSort(int n, vector

思路：

Code：

// Problem#: 21104
// Submission#: 5224600
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
class Solution {
public:
    vector topologicalSort(int n, vector<>>& edges) {
        vector result;
        vector<>> rech(n);
        queue zeroindegreeNode; 
        int indegree[1000000];
        memset(indegree, 0, sizeof(indegree));

        for (int i = 0; i < edges.size(); i++) {
            indegree[edges[i].second]++;
            rech[edges[i].first].push_back(edges[i].second);
        }
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
              zeroindegreeNode.push(i);
            }
        }

        while (result.size() < n) {
            int next = zeroindegreeNode.front();
            for (int i = 0; i < rech[next].size(); i++) {
                indegree[rech[next][i]]--;
                if (indegree[rech[next][i]] == 0) {
                    zeroindegreeNode.push(rech[next][i]);
                }
            }

            result.push_back(next);
            zeroindegreeNode.pop();
        }
        return result;
    }
};