Cod sursa(job #3000781)

Utilizator PerdevaraClaudiuPerdevara Claudiu Stefan PerdevaraClaudiu Data 12 martie 2023 20:33:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100002
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");

int n,m;
int x,y;

vector <int> G[NMAX];
priority_queue < int , vector<int> , greater<int> > H;
int di[NMAX]; //di[x]=grad int al vf x sau  -1 daca x a fost plasat pe niveluri
int nr; //nr total de noduri plasate pe nivluri
int crt[NMAX]; //nodurile de pe niv curent

void citire();
void sortare_topologica();

int main()
{
    citire();
    sortare_topologica();
    return 0;
}
void citire()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y;
        //il adaug pe y in lista de adiacenta a lui x
        G[x].push_back(y);
        di[y]++;
    }
}
void sortare_topologica()
{
    int i,x,j;
    nr=0;
    //daca gr int este 0, le punem pe primul nivel
    for(i=1;i<=n;i++)
        if(di[i]==0)
            H.push(i);

    while(nr<n) //pentru a merge prin toate nodurile
    {
            x=H.top(); //ia primul element din heap, acesta fiind minimul
            H.pop(); //il scoate din heap
            fout<<x<<' '; //se afiseaza acesta
            nr++;
            di[x]=-1;// -1 atunci cand nodul a fost plasat pe un nivel si scos din graf
            //decrementez gradele int ale vecinilor lui x
            for(j=0;j<G[x].size();j++) //iau un j cu care parcurg vecinii
            {
                di[G[x][j]]--; //scad gradul int
                if(di[G[x][j]]==0) //daca gradul int a vecinului a ajuns la 0, il bag in heap
                    //la fiecare x nou se readauga nodurile cu gradul int 0 nu stiu cum sa mai zic
                    H.push(G[x][j]);
            }
    }
}