Cod sursa(job #2834492)

Utilizator enestianEne Sebastian enestian Data 17 ianuarie 2022 09:45:21
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
//Restrictii
//1 <= N <= 100 000
//0 <= M <= minim(200 000, N * (N + 1) / 2)
//Pentru 50 % dintre teste 1 <= N <= 1 000


ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<vector<int>> v;


void citire(int n, int m) {
    int x, y;
    v.resize(n + 1);
    for (int i = 0; i < m; i++) {
        f >> x >> y;
        v[x].push_back(y);
    }
}


void DFS(vector<bool>& vizitat, int start, stack<int>& stack) {
    vizitat[start] = true;
    for (int i = 0; i < v[start].size(); i++)
        if (vizitat[v[start][i]] == false)
            DFS(vizitat, v[start][i], stack);
    stack.push(start);
}



void sortare_topologica(int n) {
    vector<bool> vizitat(n + 1, false);
    stack<int> stack;

    for (int i = 1; i <= n; ++i) {
        if (vizitat[i] == false) {
            DFS(vizitat, i, stack);
        }
    }
    for (int i = stack.size() - 1; i >= 0; i--)
    {
        int a = stack.top();
        stack.pop();
        g << a << " ";
    }
}


int main() {
    int n, m;
    f >> n >> m;

    citire(n,m);
    sortare_topologica(n);//de nr de noduri

    f.close();
    g.close();
	return 0;
}