Cod sursa(job #2130053)

Utilizator OliniciEmanuel Olinici Olinici Data 13 februarie 2018 13:30:39
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#define NMAX 50005

using namespace std;

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

void citire();
void program();

int n,m;
vector <int> gi(NMAX);
vector <int> niv(NMAX);
vector <int> lad[NMAX];

int main()
{
 citire();
 program();

    return 0;
}

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

void program()
{
int k, nr=0;
int i,j;
 while(nr<n)
      {k=1;
       for(i=1; i<=n; i++)
          {if(gi[i]==0)
              niv[k++]=i;
          }
       for(i=1; i<k; i++)
          {fout<<niv[i]<<' ';
           gi[niv[i]]=-1;
           for(j=1; j<=lad[niv[i]].size(); j++)
               gi[lad[niv[i]][j]]--;
          }
      }
}