lintcode：127 · 拓扑排序

题目来源

• lintcode

题目描述

#include <vector>

using namespace std;
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
    }
};

题目解析

拓扑序的实际意义是：按照这个顺序，在每个项目开始时，能够保证它的前驱活动都已完成，从而使整个工程顺利进行。

注意，有时候拓扑序并不是唯一的，所以面试的时候要问下面试官，是要求解任意解，还是列出所有解。

DFS