Cod sursa(job #1638762)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 8 martie 2016 08:59:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb


#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

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

vector <int> L[50005];
int N, M, cnt, viz[50005], dp[50005];

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

void DFS(int k)
{
   int i;
   viz[k] = 1;
   
   for (int j=0; j<L[k].size(); j++)  
   {
       i = L[k][j];
       if (!viz[i])
          DFS(i);
   }

   dp[++cnt] = k;
}

void Rezolva()
{
   int i;
   cnt = 0;
   for (i=1; i<=N; i++)
     if (viz[i] == 0)
           DFS(i);
}

void Afisare()
{
  int i;
  for (i=cnt; i>=1; i--) 
    fout << dp[i] << " ";
  fout << "\n";
}


int main ()
{
  Citire();
  Rezolva();
  Afisare();
  fin.close();
  fout.close();
  return 0;
}