test/topological_sort.unverified.cpp

• View this file on GitHub
• Last update: 2022-08-29 11:39:30+09:00
• Link: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=ja

Depends on

• graph/topological_sort.cpp

Code

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

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=ja"
#include "../graph/topological_sort.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    auto ret = topological_sort(G);
    for (auto &a : ret)
        cout << a << '\n';
    return 0;
}

#line 1 "test/topological_sort.unverified.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=ja"
#line 3 "graph/topological_sort.cpp"
using namespace std;

// topological_sort
// 有向グラフGの隣接リストを受け取ってDAGであればトポロジカルソートした結果を返し,
// そうでなければ{-1}を返す.
vector<int> topological_sort(const vector<vector<int>> &G) {
    int n = (int)G.size();
    vector<int> ans;
    stack<int> stk;
    vector<int> indeg(n, 0);
    for (int i = 0; i < n; i++) {
        for (const int &v : G[i])
            indeg[v]++;
    }
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) {
            stk.push(i);
            indeg[i] = -1;
        }
    }
    while (!stk.empty()) {
        int v = stk.top();
        ans.push_back(v);
        stk.pop();
        for (const int &u : G[v]) {
            if (--indeg[u] == 0) {
                stk.push(u);
                indeg[u] = -1;
            }
        }
    }
    if (all_of(indeg.begin(), indeg.end(), [](int x) { return x < 0; }))
        return ans;
    else
        return {-1};
}
#line 6 "test/topological_sort.unverified.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    auto ret = topological_sort(G);
    for (auto &a : ret)
        cout << a << '\n';
    return 0;
}

Back to top page