Cod sursa(job #2179445)

Utilizator Athena99Anghel Anca Athena99 Data 20 martie 2018 11:17:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax= 50000;
const int mmax= 100000;

bool u[nmax+1];
int k, sol[nmax+1];

vector <int> v[nmax+1];

void dfs( int x ) {
    u[x]= 1;
    for ( vector <int>::iterator it= v[x].begin(); it!=v[x].end(); ++it ) {
        if ( u[*it]==0 ) {
            dfs(*it);
        }
    }

    sol[++k]= x;
}

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1, x, y; i<=m; ++i ) {
        fin>>x>>y;
        v[x].push_back(y);
    }

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

    for ( int i= n; i>=1; --i ) {
        fout<<sol[i]<<" ";
    }
    fout<<"\n";

    return 0;
}