Cod sursa(job #2375754)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 8 martie 2019 11:57:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void dfs(int nod, vector <vector <int>> &ad, vector <bool> &viz, vector <int> &srt){
    viz[nod] = true;
    for(auto fiu : ad[nod])
        if(!viz[fiu])
            dfs(fiu, ad, viz, srt);
    srt.push_back(nod);
}

int main()
{
    int n, m, x, y;
    fin >> n >> m;
    vector <vector <int>> ad(n + 1);
    vector <bool> viz(n + 1);
    vector <int> srt;
    for(int i = 0; i < m; i++){
        fin >> x >> y;
        ad[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i, ad, viz, srt);
    reverse(srt.begin(), srt.end());
    for(auto e : srt)
        fout << e << ' ';
    fin.close();
    fout.close();
    return 0;
}