test/topological_sort.aoj.GRL_4_B.test.cpp

View this file on GitHub
Last update: 2020-05-09 18:52:06+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_B

Depends on

lib/topological_sort.hpp

Code

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

#include <iostream>
#include <vector>
#include "../lib/topological_sort.hpp"

int main() {
    int n, m; std::cin >> n >> m;
    std::vector<std::vector<int>> edg(n);
    for (int i = 0; i < m; i++) {
        int s, t; std::cin >> s >> t;
        edg[s].push_back(t);
    }
    TopologicalSort topo(edg);
    for (int i : topo.ord) std::cout << i << std::endl;
    return 0;
}

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

#include <iostream>
#include <vector>
#line 1 "lib/topological_sort.hpp"



#line 5 "lib/topological_sort.hpp"
#include <algorithm>

struct TopologicalSort {
    using Edge = std::vector<std::vector<int>>;
    std::vector<int> ord;
    bool isdag;

    TopologicalSort(const Edge &edg) : used(edg.size()) {
        isdag = true;
        for (int i = 0; i < (int)edg.size(); i++) {
            if (used[i] != 0) continue;
            isdag &= rec(edg, i);
        }
        std::reverse(ord.begin(), ord.end());
    }

private:
    std::vector<int> used;

    bool rec(const Edge &edg, int pos) {
        if (used[pos] == -1) return false;
        if (used[pos] == 1) return true;
        used[pos] = -1;
        for (int c : edg[pos]) {
            if (!rec(edg, c)) return false;
        }
        used[pos] = 1;
        ord.push_back(pos);
        return true;
    }
};


#line 6 "test/topological_sort.aoj.GRL_4_B.test.cpp"

int main() {
    int n, m; std::cin >> n >> m;
    std::vector<std::vector<int>> edg(n);
    for (int i = 0; i < m; i++) {
        int s, t; std::cin >> s >> t;
        edg[s].push_back(t);
    }
    TopologicalSort topo(edg);
    for (int i : topo.ord) std::cout << i << std::endl;
    return 0;
}