算法描述：

1 统计每个节点的入度

2 选择一个入度为0的顶点u放入结果列表

3 删除顶点u和它所有的出边，更新入度

4 回到2 迭代计算

如果结果列表的元素个数为n，说明不存在环；输出结果列表，否则输出-1，代表存在环，不存在这样一种排列

代码分析：

1 初始化数据结构

function initEdges(n, edges[maxn])

  for i -> (0, n-1)

    edges[i] = {}

2 邻接表加边

function addEdge(edge[maxn], u, v)

  edges[u].append(v)

3 建图

addEdge(graph, u1, v1, w1)

addEdge(graph, u2, v2, w2)

...

4 统计入度

function calcDegree(n, edges[maxn], deg[maxn])

  for i -> (0, n-1)

    deg[i] = 0

  for i -> (0, n-1)

    for j -> (0, edges[u].size() - 1)

      v = edges[u][i]

      deg[v] = deg[v] + 1

5 拓扑排序

function topoSort(n, edges[maxn], deg[maxn], ans)

  q = Queue()

  for i -> (0, n-1)

    if deg[i] == 0

      q.push(i)

  while(not q.empty())

    u = q.front()

    q.pop()

    ans.append(u)

    for i -> (0, edges[u].size() - 1)

      v = edges[u][i]

      deg[v] = deg[v] - 1

      if deg[v] == 0

        q.push(v)

时间复杂度为o(n+m)，n是顶点数量，m为边数量。

代码练习 1 对应蓝桥云课，走多远 代码见下

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

#define maxn 1000005

void initEdges(int n, vector<int> edges[maxn]){
  for(int i=0; i<n; ++i){
    edges[i].clear();
  }
}

void addEdge(vector<int> edges[maxn], int u, int v){
  edges[u].push_back(v);
}

bool topoSort(int n, vector<int> edges[maxn], vector<int>& ans){
  vector<int> deg;
  queue<int> q;
  ans.clear();
  for(int i=0; i<n; ++i){
    deg.push_back(0);
  }
  for(int i=0; i<n; ++i){
    for(int j=0; j<edges[i].size(); ++j){
      int v = edges[i][j];
      ++deg[v];
    }
  }
  for(int i=0; i<n; ++i){
    if(!deg[i]){
      q.push(i);
    }
  }

  while(!q.empty()){
    int u = q.front();
    q.pop();
    ans.push_back(u);
    for(int i=0; i<edges[u].size(); ++i){
      int v = edges[u][i];
      --deg[v];
      if(!deg[v]){
        q.push(v);
      }
    }
  }
  return ans.size() == n;
}

vector<int> edges[maxn];
int dp[maxn];

int main()
{
  int n, m;
  cin >> n >> m;
  while(m--){
    int u,v;
    cin >> u >> v;
    addEdge(edges, u-1, v-1);
  }
  vector<int> ans;
  bool go = topoSort(n, edges, ans);
  if(go){
    int ret = 0;
    for(int i=ans.size() - 1; i>=0; --i){
      int u = ans[i];
      dp[u] = 0;
      for(int j=0; j<edges[u].size(); ++j){
        int v = edges[u][j];
        dp[u] = max(dp[v]+1, dp[u]);
      }
      ret = max(ret, dp[u]);
    }
    cout << ret << endl;
  }else{
    cout << 0 << endl;
  }
  // 请在此输入您的代码
  return 0;
}

代码练习2，对应蓝桥云课 阿霖的旅游计划，代码见下

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

#define maxn 100005

void initEdges(int n, vector<int> edges[maxn]){
  for(int i=0; i<n; ++i){
    edges[i].clear();
  }
}

void addEdge(vector<int> edges[maxn], int u, int v){
  edges[u].push_back(v);
}

bool topoSort(int n, vector<int> edges[maxn], vector<int>& ans){
  vector<int> deg;
  queue<int> q;
  ans.clear();
  for(int i=0; i<n; ++i){
    deg.push_back(0);
  }
  for(int i=0; i<n; ++i){
    for(int j=0; j<edges[i].size(); ++j){
      int v = edges[i][j];
      ++deg[v];
    }
  }
  for(int i=0; i<n; ++i){
    if(!deg[i]){
      q.push(i);
    }
  }

  while(!q.empty()){
    int u = q.front();
    q.pop();
    ans.push_back(u);
    for(int i=0; i<edges[u].size(); ++i){
      int v = edges[u][i];
      --deg[v];
      if(!deg[v]){
        q.push(v);
      }
    }
  }
  return ans.size() == n;
}

vector<int> edges[maxn];
int a[maxn];
long long dp[maxn];

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i=0; i<n; ++i){
    cin >> a[i];
  }
  initEdges(n, edges);
  while(m--){
    int u, v;
    cin >> u >> v;
    --u, --v;
    if(a[u] < a[v]){
      addEdge(edges, u, v);
    }else if(a[v] < a[u]){
      addEdge(edges, v, u);
    }
  }
  vector<int> ans;
  long long ret = 0;
  topoSort(n, edges, ans);

  for(int i=ans.size() - 1; i>=0; --i){
    int u = ans[i];
    long long max = 0;
    for(int j=0; j<edges[u].size(); ++j){
      int v = edges[u][j];
      if(dp[v] > max){
        max = dp[v];
      }
    }
    dp[u] = max + a[u];
    if(dp[u] > ret){
      ret = dp[u];
    }
  }
  cout << ret << endl;
  // 请在此输入您的代码
  return 0;
}

代码练习3 对应蓝桥云课 恋爱通关游戏 代码见下

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

#define maxn 200005
#define eType vector<int>

void initEdges(int n, vector<eType> edges[maxn]){
  for(int i=0; i<n; ++i){
    edges[i].clear();
  }
}

void addEdge(vector<eType> edges[maxn], int u, int v, int w){
  edges[u].push_back({v, w});
}

bool topoSort(int n, vector<eType> edges[maxn], vector<int>& ans){
  vector<int> deg;
  queue<int> q;
  ans.clear();
  for(int i=0; i<n; ++i){
    deg.push_back(0);
  }
  for(int i=0; i<n; ++i){
    for(int j=0; j<edges[i].size(); ++j){
      int v = edges[i][j][0];
      ++deg[v];
    }
  }
  for(int i=0; i<n; ++i){
    if(!deg[i]){
      q.push(i);
    }
  }

  while(!q.empty()){
    int u = q.front();
    q.pop();
    ans.push_back(u);
    for(int i=0; i<edges[u].size(); ++i){
      int v = edges[u][i][0];
      --deg[v];
      if(!deg[v]){
        q.push(v);
      }
    }
  }
  return ans.size() == n;
}

vector<eType> edges[maxn];
long long dp[maxn];

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i=0; i<m; ++i){
    int A, B, C;
    cin >> A >> B >> C;
    --A, --B;
    addEdge(edges, A, B, C);

  }
  vector<int> ans;
  int ret = 0;
  topoSort(n, edges, ans);
  dp[0] = 0;
  for(int i=1; i<n; ++i){
    dp[i] = -1e9;
  }
  for(int i=0; i<ans.size(); ++i){
    int u = ans[i];
    for(int j=0; j<edges[u].size(); ++j){
      int v = edges[u][j][0];
      int w = edges[u][j][1];
      dp[v] = max(dp[v], dp[u] + w);     
    }
  }

  for(int i=0; i<n; ++i){
    if(dp[i] >= 100 && edges[i].empty()){
      ++ret;
    }
  }
  cout << ret << endl;
  // 请在此输入您的代码
  return 0;
}