Cod sursa(job #2867991)

Utilizator marcpopPop Marc Alexandru marcpop Data 10 martie 2022 17:57:53
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, a, b;

bool viz[50002];

vector<int> v[50002];

vector<int> e;

void dfs(int start) {

    viz[start] = 1;

    for (int i=0; i<v[start].size(); i++) {

        if (!viz[v[start][i]]) {

            dfs(v[start][i]);
        }
    }

    e.push_back(start);

}

void topSort(int n) {

    for (int i=1; i<=n; i++) {
        if (!viz[i]) {
            dfs(i);
        }
    }

}

int main()
{

    fin>>n>>m;

    for (int i=1; i<=m; i++) {

        fin>>a>>b;

        v[a].push_back(b);

    }

    topSort(n);

    for (int i=e.size()-1; i>=0; i--) {
        fout<<e[i]<<" ";
    }

    return 0;
}