Cod sursa(job #2857931)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 26 februarie 2022 17:36:20
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

void dfs(
    int i,
    const vector<vector<int>> &adj,
    vector<bool> &vizitat,
    stack<int> &rez)
{
    stack<pair<int,int>> st;
    st.push({i,0});
    vizitat[i] = true;

    while (!st.empty()) {
        int nod = st.top().first;
        int &i = st.top().second;

        if (i < adj[nod].size()) {
            int vecin = adj[nod][i];
            ++i;

            if (!vizitat[vecin]) {
                vizitat[vecin] = true;
                st.push({vecin, 0});
            }
        }
        else {
            rez.push(nod);
            st.pop();
        }
    }
}


int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int n,m;
    fin >> n >> m;

    vector<vector<int>> adj(n+1);

    for (int i = 0; i < m; ++i) {
        int a,b;
        fin >> a >> b;

        adj[a].push_back(b);
    }

    stack<int> rez;

    vector<bool> vizitat(n+1, false);

    for (int i = 1; i <= n; ++i)
        if (!vizitat[i])
            dfs(i, adj, vizitat, rez);

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

    fout << endl;

    return 0;
}