Determining an Order of Courses

题目链接：pdf

题目给出一个有向图，保证没有环，求这个有向图所有点的拓扑排序之后的序列， 只输出一种即可。

同样用DFS，求拓扑排序的过程一般是先求所有出度为0的点，然后删除这些点， 如此循环。DFS的过程中，回退过程最早的那个点一定是出度为0，所以就可以记 录下DFS的过程中每个点回退的时刻，然后按照时刻大小逆序排序就是拓扑顺序 了。

// Sat May 13 00:14:15 CST 2017
// Sat May 13 09:27:41 CST 2017


// 拓扑排序

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int, int> PII;
vector<PII > post;	// index, clock_cnt
int clock_cnt;

void dfs(vector<vector<int> > &adj, vector<int> &used, int x) {
  used[x] = true;

  for (auto v : adj[x]) {
    if (!used[v]) {
      dfs(adj, used, v);
    }
  }

  clock_cnt++;
  post.push_back(make_pair(x, clock_cnt));
}

vector<int> toposort(vector<vector<int> > adj) {
  vector<int> used(adj.size(), 0);
  vector<int> order;

  for (size_t i = 0; i < adj.size(); ++i) {
    if (!used[i]) dfs(adj, used, i);
  }

  sort(post.begin(), post.end(),
       [](const PII &a, const PII &b) -> bool { return a.second > b.second; }); // 不能糊涂。。。

  for (auto &a: post) {
    order.push_back(a.first);
  }
  
  return order;
}

int main() {
  size_t n, m;
  cin >> n >> m;
  // while (std::cin >> n >> m) {
  vector<vector<int> > adj(n, vector<int>());
  post.clear();
  clock_cnt = 1;
  
  for (size_t i = 0; i < m; i++) {
    int x, y;
    std::cin >> x >> y;
    adj[x - 1].push_back(y - 1);
  }
    
  vector<int> order = toposort(adj);
    
  for (size_t i = 0; i < order.size(); i++) {
    std::cout << order[i] + 1 << " ";
  }
  cout << "\n";
  // }

  return 0;
}