Cod sursa(job #2517583)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 3 ianuarie 2020 19:43:48
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <set>
#include <iterator>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m, a, b;
bool f[50100];
set<int, greater<int> > ord;
stack<int> sol;
stack<int> st;

struct str {
    vector<int> v;
} s[100100], d[100100];

void ins(int a) {
    st.push(a);
    for (int i = 0; i < s[a].v.size(); i++)
        if (!f[s[a].v[i]]) {
            f[s[a].v[i]] = true;
            ins(s[a].v[i]);
        }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> a >> b;
        s[a].v.push_back(b);
        d[b].v.push_back(a);
        ord.insert(b);
    }


    for (set<int, greater<int> >::iterator itr = ord.begin(); itr != ord.end(); itr++) {
        f[*itr] = true;
        ins(*itr);
        while (!st.empty()) {
            sol.push(st.top());
            st.pop();
        }
    }

    for (int i = 1; i <= n; i++)
        if (!f[i])
            sol.push(i);

    while (!sol.empty()) {
        fout << sol.top() << ' ';
        sol.pop();
    }

    return 0;
}