Cod sursa(job #2796335)

Utilizator DianaZaharia132nr2Zaharia Diana Cristiana DianaZaharia132nr2 Data 7 noiembrie 2021 22:08:43
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include<unordered_map>
#include<queue>
#include<fstream>
using namespace std;

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

int N,M,a,b;
vector<int> m[100001]; //ca sa pot sa am aceasi cheie , fac lista de adiacenta
int d[50000];//grad intern
queue<int>ord;//coada

void st(int v)
{
    d[v]=1;//initializam cu 1
    for(int i=m[v].begin;i<=m[v].end;++i)// daca lista de adiacenta a varfului nu e goala facem recursiv pt elementele din interior care o au goala
    {
        if(d[i]==0)
            sortare_topologica(i);
    }
    ord.push(v);//daca e goala scriem
}

int main()
{
    cin>>N>>M;
    for(int i=1;i<=M;++i) //construire lista adiacenta
    {
        cin>>a>>b;
        m[a].push_back(b);
    }


    for(int i=1;i<=N;++i) // iau lista de adiacenta la rand
    {
        if(d[i]==0)
            st(i);
    }

    while(!ord.empty())//afisare coada
        {
            cout<<ord.front()<<" ";
            ord.pop();
        }

    return 0;
}