Cod sursa(job #593167)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 iunie 2011 16:52:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

vector <long> G[50005];
deque <long> S;
long N;
bool V[50005];

void Read ()
{
    ifstream fin ("sortaret.in");
    long i, M, X, Y;
    fin >> N >> M;
    for (i=0; i<M; i++)
    {
        fin >> X >> Y;
        G[X].push_back (Y);
    }
    fin.close ();
}

void Type ()
{
    ofstream fout ("sortaret.out");
    unsigned long i;
    for (i=0; i<S.size (); i++)
    {
        fout << S[i] << " ";
    }
    fout << "\n";
    fout.close ();
}

void DFS (long X)
{
    unsigned long i;
    V[X]=true;
    for (i=0; i<G[X].size (); i++)
    {
        if (V[G[X][i]]==false)
        {
            DFS (G[X][i]);
        }
    }
    S.push_front (X);
}

int main()
{
    long i;
    Read ();
    for (i=1; i<=N; i++)
    {
        if (V[i]==false)
        {
            DFS (i);
        }
    }
    Type ();
    return 0;
}