Cod sursa(job #2648323)

Utilizator LeCapataIustinian Serban LeCapata Data 10 septembrie 2020 11:29:22
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <queue>
#define N 50005
using namespace std;

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

vector< vector<int> > muchii(2*N);
vector<int> rezultat;
queue<int> coada;
bool fol[N];
int n, m;

void dfs(){
    int nod = coada.front();
    coada.pop();
    fol[nod] = 1;

    for(size_t i = 0; i < muchii[nod].size(); ++i)
        if(!fol[muchii[nod][i]]){
            coada.push(muchii[nod][i]);
            dfs();
        }
    rezultat.push_back(nod);
}

int main()
{
    in>>n>>m;

    for(int i = 1; i <= m; ++i){
        int x, y;
        in>>x>>y;
        muchii[x].push_back(y);
    }
    for(int i = 1; i <= n; ++i)
        if(!fol[i]){
            coada.push(i);
            dfs();
        }

    for(int i = rezultat.size() - 1; i >= 0; --i)
        out<<rezultat[i]<<" ";

    in.close();
    out.close();
    return 0;
}