几个月前，看到这样一道题：有若干个任务，都是以数字来表示任务ID，任务之间有依赖关系，比如：1 <- 2，表示任务2依赖于任务1，即，必须先完成任务1，才能完成任务2.那么现在给定多个这样的任务依赖关系，请设计并实现算法，其输出是一个任务序列，使得所有任务都可以被依次完成（即满足所有依赖关系）。

而几个月后的前不久，工作中又遇到这样一个问题，有若干个library，互相之间有依赖关系，请设计并实现一个算法，以输出一个library的序列，使得它们可以被按此序列顺利加载。

所以你看，其实这2个问题是同一个问题。那么怎么做呢？其实并不难，但其中有一个很关键的点。只要想透了这个点，一切就迎刃而解了。这个点，一句话说破了也很简单，如果不说破，可能也会困扰不少人。一句话，每一次都找出所有的无依赖任务。这就很容易理解了：

维护若干个依赖链，第一次，先找出所有的无依赖任务，然后将这些任务从依赖链中删除并添加到结果列表；

然后再找出所有的无依赖任务，再将它们从依赖链中删除并添加到结果列表；

如此循环往复，直到以下2种情况的任意一种发生为止：

1. 正常情况：所有的依赖链为空，即所有任务都被移到了结果列表；

2. 异常情况：仍有若干条依赖链不为空，但已经找不出无依赖任务了。这是为什么呢？聪明的读者想一想吧，不解释了。

最后，实现代码如下（115行的C++代码搞定，其实还能更短一点）：

#include <vector>
#include <set>
#include <iostream>
using namespace std;

// The original dependency sequences.
const vector<vector<int>> dependencyVec = {
  {1,2 },{3,4,5},{2,6},3 }  
};

// A copy of dependencyVec,but it will be changed during calculation
vector<vector<int>> calcVec = dependencyVec;

// This function is just print the dependency sequencies in run time for debug purpose.
void printCalcVec()
{
  cout << "caclVec is as below: " << endl;
  for (auto vec : calcVec) {
    for (int i : vec) {
      cout << i << ",";
    }
    cout << endl;
  }
  cout << "----------------" << endl;
}

set<int> collectNoDependencyItems()
{
  set<int> noDependItems = {};

  // Store the headers of each dependency sequence.
  set<int> headers = {};
  for (auto vec : calcVec) {
    if (vec.size() > 0) headers.insert(vec[0]);
  }

  for (int h : headers) {
    bool noDepend = true;
    for (auto vec : calcVec) {
      for (unsigned int count = 1; count < vec.size(); ++count) {
        if (h == vec[count]) {
          noDepend = false;
          break;
        }
      }
      if (!noDepend) break;
    }

    if (noDepend) noDependItems.insert(h);
  }

  cout << "No Dependencies: ";
  for (int t : noDependItems) {
    cout << t << ",";
  }
  cout << endl << "----------------" << endl;

  return noDependItems;
}

void generateOrderList()
{
  // This is the final order list.
  vector<int> finalList{};

  // Check if calcVec is empty. If yes,Done.
  while (calcVec.size() > 0) {
    printCalcVec();

    // Figure out no dependency items and push them to finalList
    set<int> noDependItems = collectNoDependencyItems();

    if (noDependItems.size() == 0) {
      cout << "NoDependItems = 0" << endl;
      // There is no item which is no dependent. This means there is loop dependency.
      break;
    }

    // Push no dependent items to finalList
    for (unsigned int i : noDependItems) {
      finalList.push_back(i);
    }

    // Remove the headers of each dependency sequence which are no dependent items
    for (int i = 0; i < calcVec.size(); ) {
      if (noDependItems.find(calcVec[i][0]) != noDependItems.end()) {
        calcVec[i].erase(calcVec[i].begin());
      }
      if (calcVec[i].size() == 0) {
        calcVec.erase(calcVec.begin() + i);
      }
      else {
        ++i;
      }
    }
  }

  cout << "FinalList: ";
  for (int i : finalList) {
    cout << i << ",";
  }
  cout << endl;
}


int main()
{
  generateOrderList();
  return 0;
}

caclVec is as below:
1,2,3,5,6,----------------
No Dependencies: 1,----------------
caclVec is as below:
2,----------------
No Dependencies: 2,----------------
caclVec is as below:
3,----------------
No Dependencies: 3,----------------
caclVec is as below:
4,----------------
No Dependencies: 4,----------------
caclVec is as below:
5,----------------
No Dependencies: 5,----------------
FinalList: 1,Press any key to continue . . .