graph/topological-sort.cpp

Back to top page

• category: graph
• View this file on GitHub
  • Last commit date: 2020-09-01 17:20:31+09:00

Verified with

• test/topological-sort.test.cpp

Code

vector<int> topologicalSort(const UnWeightedGraph &g) {
    const size_t n = g.size();
    vector<int> ans, seen(n);
    auto dfs = [&g, &seen, &ans](auto &&f, int v) {
        if (seen[v])
            return;
        seen[v] = true;
        for (auto nv : g[v])
            f(f, nv);
        ans.push_back(v);
    };
    for (size_t i = 0; i < n; ++i)
        dfs(dfs, i);
    if (ans.size() != n)
        return vector<int>();
    reverse(ans.begin(), ans.end());
    return ans;
}

#line 1 "graph/topological-sort.cpp"
vector<int> topologicalSort(const UnWeightedGraph &g) {
    const size_t n = g.size();
    vector<int> ans, seen(n);
    auto dfs = [&g, &seen, &ans](auto &&f, int v) {
        if (seen[v])
            return;
        seen[v] = true;
        for (auto nv : g[v])
            f(f, nv);
        ans.push_back(v);
    };
    for (size_t i = 0; i < n; ++i)
        dfs(dfs, i);
    if (ans.size() != n)
        return vector<int>();
    reverse(ans.begin(), ans.end());
    return ans;
}

Back to top page