Cod sursa(job #2313656)

Utilizator BotezatuGabrielBotezatu Gabriel Eugen BotezatuGabriel Data 7 ianuarie 2019 11:58:11
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
#define N 5005
using namespace std;

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

vector <int> G[N];
int n, m;

bool viz[N]; /// pentru Dfs
stack <int> S;  /// memorarea nodurilor in ordinea timpilor de final;

void Citire()
{
  int c,y,i,x;
  fin>>n>>m;
  for(i=1; i<=m; ++i)
  {
      fin>>x>>y;
      G[x].push_back(y);
  }


}

void DFS(int x)
{
    viz[x]=1;
    for( int i=0; i<G[x].size(); ++i)
        if(!viz[G[x][i]])
        DFS(G[x][i]);
    S.push(x);


}

void SortareTopologica()
{
    int i;
    for(i=1; i<=n; ++i)
        if(!viz[i]) DFS(i);

}

void Afisare()
{
    while (!S.empty())
    {
        fout<<S.top()<<" ";
        S.pop();
    }
}


int main()
{
    Citire();
    SortareTopologica();
    Afisare();


    return 0;
}