test/aoj/grl_4_b.test.cpp

View this file on GitHub
Last update: 2023-01-28 17:23:21+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_B

Depends on

src/graph/topological_sort.hpp

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_B"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/graph/topological_sort.hpp"

int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<int>> g(V);
  for (int i = 0; i < E; ++i) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
  }
  auto res = topological_sort(g);
  for (int v : res) {
    cout << v << endl;
  }

  return 0;
}

#line 1 "test/aoj/grl_4_b.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_B"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/graph/topological_sort.hpp"

#line 4 "src/graph/topological_sort.hpp"
using namespace std;

template <typename T = int>
vector<int> topological_sort(vector<vector<int>> g) {
  vector<int> res;
  vector<bool> seen(g.size());
  auto dfs = [&](auto dfs, int v) -> void {
    seen[v] = true;
    for (int to : g[v]) {
      if (seen[to]) {
        continue;
      }
      dfs(dfs, to);
    }
    res.push_back(v);
  };
  for (int v = 0; v < (int)g.size(); ++v) {
    if (seen[v]) {
      continue;
    }
    dfs(dfs, v);
  }
  reverse(res.begin(), res.end());
  return res;
}
#line 8 "test/aoj/grl_4_b.test.cpp"

int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<int>> g(V);
  for (int i = 0; i < E; ++i) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
  }
  auto res = topological_sort(g);
  for (int v : res) {
    cout << v << endl;
  }

  return 0;
}