# 目次

• 目次
• 問題
• 解説
• 解答

# 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

# 解説

トポロジカルソートとは、有向グラフの矢印が指す順番を守りながらー直線上に頂点を並べることである.
まずどこからも入力がない頂点から開始して、頂点を出力.
頂点をグラフから切り離して辺も削除する.
すると次の入力が無い辺ができるのでその頂点を出力する.
入力が無い頂点が見つからない場合は、一旦すべての未訪問の頂点を調べて入力が無いものから再出発する.

# 解答

BFSで実装した例.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

void tsort(vector<Int> edges[], Int n, vector<Int> &indeg, vector<Int> &result) {
  vector<bool> done(n, false);
  queue<Int> Q;
  
  Int index = 0;
  loop(i,0,n) {
    if (indeg[i] > 0 || done[i]) continue;
    Q.push(i);
    done[i] = i;
    result[index++] = i;
    
    while (!Q.empty()) {
      Int u = Q.front(); Q.pop();
      for (Int v: edges[u]) {
        indeg[v]--;
        if (indeg[v] > 0 || done[v]) continue;
        Q.push(v);
        done[v] = true;
        result[index++] = v;
      }
    }
  }
}


int main(void) {
  Int n, e, u, v;
  cin >> n >> e;
  vector<Int> edges[n];
  vector<Int> indeg(n, 0);
  loop(i,0,e) {
    cin >> u >> v;
    edges[u].push_back(v);
    indeg[v]++;
  }
  
  vector<Int> result(n, 0);
  tsort(edges, n, indeg, result);
  loop(i,0,n) cout << result[i] << ' ';
  cout << endl;
  return 0;
}