Cod sursa(job #2127974)

Utilizator IustinSSurubaru Iustin IustinS Data 11 februarie 2018 12:17:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#define nmax 50001
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n,m;
vector <int> lista[nmax];
int gr[nmax];
int fol;
int afis[nmax];
bool uz[nmax];

void citire();
void descompunere();
int main()
{
    citire();
    descompunere();
    return 0;
}
void citire()
{
   int i,x,y;
   fin>>n>>m;
   for (i=1; i<=m; i++)
      {
         fin>>x>>y;
         lista[x].push_back(y);
         gr[y]++;
      }
}
void descompunere()
{
   int i,j,k;
   while (fol<n)
      {  k=0;
         for (i=1; i<=n; i++)
            if (!gr[i] && !uz[i])
                  {afis[++k]=i;
                   fol++;
                   uz[i]=1;
                  }
         for (i=1; i<=k; i++)
            for (j=0; j<lista[afis[i]].size(); j++)
               gr[lista[afis[i]][j]]--;
      for (i=1; i<=k; i++)
         fout<<afis[i]<<' ';
      }
}