Cod sursa(job #1547673)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 9 decembrie 2015 18:51:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int NMax = 50005;
int N,M;
int Use[NMax];
int O[NMax],k;
vector<int> G[NMax];

void Read()
{
    fin>>N>>M;

    for(int i = 1; i<=M; i++)
        {
            int x,y;
            fin>>x>>y;
            G[x].push_back(y);
        }
}


void DFS(int Nod)
{
    Use[Nod] = 1;
    for(int i = 0; i< (int)G[Nod].size(); i++)
        {
            int Vecin = G[Nod][i];
            if(!Use[Vecin])
                {
                    DFS(Vecin);
                }
        }
    O[++k] = Nod;
}
void Solve()
{
    for(int i = 1; i<=N; i++)
        if(!Use[i])
            DFS(i);
}
void Print()
{
    for(int i = N; i>=1; i--)
        fout<<O[i]<<" ";
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}