src/graph/topological_sort.hpp

• View this file on GitHub
• Last update: 2023-01-28 17:23:21+09:00
• Include: #include "src/graph/topological_sort.hpp"

Verified with

• test/aoj/grl_4_b.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
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 2 "src/graph/topological_sort.hpp"

#include <bits/stdc++.h>
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;
}

Back to top page