# Topological Sorting

Question:
http://www.lintcode.com/en/problem/topological-sorting/
Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

``````/**
* Definition for Directed graph.
* struct DirectedGraphNode {
*     int label;
*     vector<DirectedGraphNode *> neighbors;
*     DirectedGraphNode(int x) : label(x) {};
* };
*/

class Solution {
public:
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
int len = graph.size();
map<DirectedGraphNode*, int> indegree;
for (auto node : graph)
indegree[node] = 0;
for (auto node : graph) {
for (auto nn : node->neighbors) {
indegree[nn] = indegree[nn] + 1;
}
}
stack<DirectedGraphNode*> st;
for (auto dp : indegree) {
if (dp.second == 0)
st.push(dp.first);
}
vector<DirectedGraphNode*> result;
while (!st.empty()) {
DirectedGraphNode* node = st.top();
result.push_back(node);
st.pop();
for (auto nn : node->neighbors) {
indegree[nn] = indegree[nn] - 1;
if (indegree[nn] == 0)
st.push(nn);
}
}
return result;
}
};
``````