127-拓扑排序
思路
使用广度优先搜索，首先统计图中所有节点的入度，若入度为0，则此结点无前驱，可以将其输出，之后，将此结点所有后继节点的入度减1
code
/**
* 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) {
// write your code here
int size = graph.size(), i = 0;
if(size <= 0) {
return vector<DirectedGraphNode*>();
}
vector<DirectedGraphNode*> result;
queue<DirectedGraphNode*> noPreNode;
map<DirectedGraphNode*, int> nodeIndegree;
getIndegree(graph, nodeIndegree);
for(i=0; i<size; i++) {
if(nodeIndegree[graph[i]] == 0) {
noPreNode.push(graph[i]);
}
}
while(!noPreNode.empty()) {
result.push_back(noPreNode.front());
for(i=0; i<noPreNode.front()->neighbors.size(); i++) {
if(--nodeIndegree[noPreNode.front()->neighbors[i]] == 0) {
noPreNode.push(noPreNode.front()->neighbors[i]);
}
}
noPreNode.pop();
}
return result;
}
void getIndegree(vector<DirectedGraphNode*> graph, map<DirectedGraphNode*, int> &nodeIndegree) {
int size = graph.size();
for(int i=0; i<size; i++) {
int size2 = graph[i]->neighbors.size();
for(int j=0; j<size2; j++) {
nodeIndegree[graph[i]->neighbors[j]]++;
}
}
}
};