LintCode(127) Topological Sorting Show result

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.

Have you met this question in a real interview? 

Yes

Example

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Note

You can assume that there is at least one topological order in the graph.

有向图的排序，基本上还是考察概念

遍历所有给定node的neighbors， 来mark 每一个被遍历的node的边数，因为是neighbors,所以必然有至少一个与他相连， 而没有被遍历到的自然为第一个被排出的。 然后push到q上去，想象把这个node从图中拿掉，那么他所有的neighbor必然少一条边，这个时候再减少计数，如果归零，则push到q上去。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/** * 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. */ typedef DirectedGraphNode Node; vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) { // write your code here unordered_map<Node*, int> map; for (int i=0; i<graph.size(); i++){ Node* node = graph[i]; for (int j=0; j<node->neighbors.size(); j++){ Node* neighbor = node->neighbors[j]; if (map.find(neighbor) == map.end()) map[neighbor]=1; else map[neighbor]++; } } vector<Node*> result; queue<Node*> fifo; for (int i=0; i<graph.size(); i++){ if (map.find(graph[i]) == map.end()){ fifo.push(graph[i]); result.push_back(graph[i]); } } while(!fifo.empty()){ Node* node = fifo.front(); fifo.pop(); for (int i=0; i<node->neighbors.size(); i++){ Node* neighbor = node->neighbors[i]; if (--map[neighbor] == 0){ fifo.push(neighbor); result.push_back(neighbor); map.erase(neighbor); } } } return result; } };