test/aoj/notest.GRL_4_B.cpp

View this file on GitHub
Last update: 2022-07-24 22:27:49+09:00
Link: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B"
// 複数解候補がある問題で、ACでもoj-verifyのcheckではWAになりうるのでテスト対象から外す
#include "../../graph/topological-sort.hpp"

#include <iostream>
using namespace std;

using G = Graph<int>;
int main() {
  int V, E; cin >> V >> E;
  G graph(V);
  for (int i = 0; i < E; ++i) {
    int s, t; cin >> s >> t;
    graph[s].emplace_back(s, t);
  }
  vector<int> order = topologicalSort(graph);
  for (int v: order) { cout << v << endl; }
}

#line 1 "test/aoj/notest.GRL_4_B.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B"
// 複数解候補がある問題で、ACでもoj-verifyのcheckではWAになりうるのでテスト対象から外す
#line 1 "graph/topological-sort.hpp"


// @title トポロジカルソート 
#include <vector>
#include <stack>
#line 1 "graph/template.hpp"



#include <iostream>
#line 6 "graph/template.hpp"

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 7 "graph/topological-sort.hpp"

template< typename G >
std::vector<int> topologicalSort(const G &g) {
  // トポロジカルソートした結果を返す
  const int V = g.size();
  std::vector<int> indegree(V); // 200000とかだと遅い？ 厳しそうならグローバル変数にする
  // 入次数の初期化. ほんとは読み込み時にやったほうが効率が良いけど許容する
  for (int v = 0; v < V; ++v) {
    for (auto& e: g[v]) ++indegree[e.to];
  }

  std::stack<int> st;
  for (int v = 0; v < V; ++v) {
    // 入次数0の点をstackにいれる
    if (indegree[v] == 0) st.push(v);
  }

  std::vector<int> order;
  while (!st.empty()) {
    int v = st.top(); st.pop();
    order.push_back(v);
    for (auto& e: g[v]) {
      --indegree[e.to];
      if (indegree[e.to] == 0) st.push(e.to);
    }
  }

  return order;
}


#line 4 "test/aoj/notest.GRL_4_B.cpp"

#line 6 "test/aoj/notest.GRL_4_B.cpp"
using namespace std;

using G = Graph<int>;
int main() {
  int V, E; cin >> V >> E;
  G graph(V);
  for (int i = 0; i < E; ++i) {
    int s, t; cin >> s >> t;
    graph[s].emplace_back(s, t);
  }
  vector<int> order = topologicalSort(graph);
  for (int v: order) { cout << v << endl; }
}