Cod sursa(job #3000412)

Utilizator AndreiStreheStreche Andrei Claudiu AndreiStrehe Data 12 martie 2023 13:51:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

#define nmax 50001

vector <int> a[nmax];
vector <int> b[nmax];
vector <int> rez;
queue <int> coada;

int i,n,m,k1,k2,nodcurent,vecin;

void sortaretopologica()
{
    while(coada.empty()==0)
    {
        nodcurent=coada.front();
        coada.pop();
        for(i=0;i<b[nodcurent].size();i++)
        {
            vecin=b[nodcurent][i];
            a[vecin].pop_back();
            if(a[vecin].size()==0)
            {
                rez.push_back(vecin);
                coada.push(vecin);
            }
        }
    }

}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>k1>>k2;
        a[k2].push_back(k1);
        b[k1].push_back(k2);
    }
    for(i=1;i<=n;i++)
    {
        if(a[i].size()==0)
        {
            coada.push(i);
            rez.push_back(i);
        }
    }

    sortaretopologica();


    for(i=0;i<rez.size();i++)
        g<<rez[i]<<" ";

    return 0;
}