Cod sursa(job #1799532)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 6 noiembrie 2016 14:13:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("sortaret.in" );
ofstream g("sortaret.out");

int N, M, X, Y;

vector<int> A[50005];
int ordine[50005], viz[50005], nr;

void DFS(int x)
{
    viz[x] = 1;

    for ( vector<int>::iterator it = A[x].begin(); it!=A[x].end(); it++ )
        if ( !viz[*it] ) DFS(*it);

    ordine[++nr] = x;
}


int main()
{
    f >> N >> M;

    for (int i=1; i<=M; i++)
    {
        f >> X >> Y;

        A[X].push_back(Y);
    }

    for (int i=1; i<=N; i++)
        if ( !viz[i] ) DFS(i);


    for ( int i=N; i>=1; i-- )
        g << ordine[i] << ' ';
}