Cod sursa(job #2067324)

Utilizator frumcrsFrum Cristian-Mihai frumcrs Data 16 noiembrie 2017 10:39:14
Problema Sortare topologica Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
#define NMAX 50100
int grad_in[100];
vector<int> coada;
vector<int> a[NMAX];
int viz[NMAX];
int grad_ext[NMAX];

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

int main()
{
    int n,m,i,x,y,j,k;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        grad_in[y]++;
        grad_ext[x]++;

    }
    for(i=1;i<=n;i++)
    {
       for(j=1;j<=n;j++)
       {
           if(!grad_in[j] && !viz[j])
           {
               fout<<j<<" ";
               viz[j]=1;
               for(k=0;k<a[j].size();k++)
               {
                   grad_in[a[j][k]]--;
                   if(grad_in[a[j][k]]==0 && grad_ext[a[j][k]]==0)
                   {
                       viz[a[j][k]]=1;
                       fout<<a[j][k]<<" ";
                   }
               }
               break;
           }
       }
    }
}