Cod sursa(job #2207753)

Utilizator bogdan_vilculescuVilculescu Mihai-Bogdan bogdan_vilculescu Data 26 mai 2018 17:32:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

void dfs(int i, vector<bool>& viz, vector<int>* la, stack<int>& stiva) {

    viz[i] = true;
    for (int j = 0; j < la[i].size(); j++) {

        int vecin = la[i][j];
        if (viz[vecin] == 0)
            dfs(vecin, viz, la, stiva);
    }
    stiva.push(i);
}

vector<int> sortareaTopologica(int n, stack<int>& stiva, vector<bool>& viz, vector<int>* la) {
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i, viz, la, stiva);

    vector<int> sortare;
    while (!stiva.empty()) {

        int nod = stiva.top();
        stiva.pop();
        sortare.push_back(nod);
    }
    return sortare;
}

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

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

    vector<int> la[n + 1];
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;

        la[x].push_back(y);
    }

    vector<bool> viz(n+1, false);
    stack<int> stiva;

    vector<int> sortare = sortareaTopologica(n, stiva, viz, la);

    for (int i = 0; i < sortare.size(); i++) {
        fout << sortare[i] << " ";
    }
    fout << "\n";

    fin.close();
    fout.close();
    return 0;
}