Cod sursa(job #1040418)

Utilizator dnprxDan Pracsiu dnprx Data 24 noiembrie 2013 15:10:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<vector>

using namespace std;

vector<int> L[50002];
int n, viz[50002], lista[50002], k;

void Citire()
{
  int i, x, y, m ;
  ifstream fin("sortaret.in");
  fin >> n >> m;

  for (i = 1; i <= m; i++)
  {
    fin >> x >> y ;
    L[x].push_back(y);
  }
  fin.close();
}

void DFS(int nod)
{
     int j;
     viz[nod] = 1;
     for (unsigned int p = 0; p < L[nod].size(); p++)
     {
         j = L[nod][p];
         if (viz[j] == 0)
             DFS(j);
     }
     viz[nod] = 2;
     lista[++k] = nod;
}

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

void Afisare()
{
    int i;
    ofstream fout("sortaret.out");
    for (i = k; i >= 1; i--)
        fout << lista[i] << " ";
    fout.close();
}

int main()
{
  Citire();
  SortareTopologica();
  Afisare();
  return 0;
}