Cod sursa(job #2419622)

Utilizator CameliaSSamoilescu Camelia CameliaS Data 8 mai 2019 22:57:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include<vector>
#include<fstream>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
#define NMAX 50005

vector<int> graphR[NMAX];

int n, m;
int gradExt[NMAX], viz[NMAX];

struct nod{
    int info;
    nod* urm;
};

nod* lista = NULL;

void citire(){
    f>>n>>m;
    for(int i = 0; i < m; i ++)
    {
        int a,b;
        f>>a>>b;
        gradExt[a]++;
        graphR[b].push_back(a);

    }
}
void add(int node){
    nod* p = new nod;
    p->info = node;
    p->urm = lista;
    lista = p;
}

void SortTop(){
    int ok = 0;
    while(!ok)
    {
        ok = 1;
        for(int i = 1; i <= n; i ++)
            if(!viz[i] && gradExt[i]== 0)
                {
                add(i);
                viz[i] = 1;
                for(int j = 0; j < graphR[i].size(); j ++)
                    gradExt[graphR[i][j]] --;
                ok = 0;
                }
    }
}

void afisare(){
while(lista != NULL)
{
    g<<lista->info<<" ";
    lista = lista->urm;
}
}

int main()
{
   citire();
   SortTop();
   afisare();
return 0;
}