GRL_4_B Topological sort

Calendar Clock iconCalendar Clock icon


Table of contents

# Problem

# Solution

With 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;
    done[i] = i;
    result[index++] = i;
    while (!Q.empty()) {
      Int u = Q.front(); Q.pop();
      for (Int v: edges[u]) {
        if (indeg[v] > 0 || done[v]) continue;
        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;
  vector<Int> result(n, 0);
  tsort(edges, n, indeg, result);
  loop(i,0,n) cout << result[i] << ' ';
  cout << endl;
  return 0;

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!