//#include #include #include #include #include #include #include #include using std::vector; using std::pair; using namespace std; // https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes template vector sort_indexes(const vector& v) { // initialize original index locations vector idx(v.size()); iota(idx.begin(), idx.end(), 0); // sort indexes based on comparing values in v // using std::stable_sort instead of std::sort // to avoid unnecessary index re-orderings // when v contains elements of equal values stable_sort(idx.begin(), idx.end(), [&v](size_t i1, size_t i2) {return v[i1] > v[i2]; }); return idx; } void postVisit(int v, vector& clock, vector& postV) { postV[v] = clock[0]; clock[0] = clock[0] + 1; } void explore(int v, vector> &adj, vector& visited, vector& postV, vector& clock) { visited[v] = true; for (int w : adj[v]) { if (!visited[w]) explore(w, adj, visited, postV, clock); } postVisit(v, clock, postV); } void dfs(vector >& adj, vector& visited, vector& postV, vector& clock) { for (size_t v = 0; v < adj.size(); v++) { if (!visited[v]) explore(v, adj, visited, postV, clock); } } vector toposort(vector > adj) { vector visited(adj.size(), false); vector order; vector postV(adj.size(), 0); vector clock(1, 0); dfs(adj, visited, postV, clock); for (auto i : sort_indexes(postV)) { order.push_back(i); } return order; } int main() { size_t n, m; std::cin >> n >> m; vector > adj(n, vector()); for (size_t i = 0; i < m; i++) { int x, y; std::cin >> x >> y; adj[x - 1].push_back(y - 1); } vector order = toposort(adj); for (size_t i = 0; i < order.size(); i++) { std::cout << order[i] + 1 << " "; } } //TEST(Acyclicity, ac1) { // vector> adj = { { 1 }, { 2 }, { 0 }, { 0 } }; // ASSERT_EQ(acyclic(adj), 1); //}