Cod sursa(job #2130040)

Utilizator PristandaAmaliaPristanda Amalia PristandaAmalia Data 13 februarie 2018 13:21:22
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");

void citire();
void desc();

int gi[50002], niv[50002];
int n, m;
vector< vector<int> > L;

int main()
{citire();
 desc();
 return 0;
}

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

void desc()
{int  i, j, nr=0, lungniv=0;
 while(nr<n)
     {lungniv=0;
      for (i=1; i<=n; i++)
           if (gi[i]==0)
              {lungniv++;
               niv[lungniv]=i;
               nr++;
              }
      for (i=1; i<=lungniv; i++)
           fout<<niv[i]<<' ';
      for (i=1; i<=n; i++)
           if (gi[i]==0)
               gi[i]=-1;
      for (i=1; i<=lungniv; i++)
           for (j=1; j<=L[niv[i]][0]; j++)
                gi[L[niv[i]][j]]--;
     }
}