Cod sursa(job #2796372)

Utilizator DianaZaharia132nr2Zaharia Diana Cristiana DianaZaharia132nr2 Data 7 noiembrie 2021 22:55:57
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
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
unordered_map<int,bool>d;//grad intern redus la 0 are grad 0,1 are alt grad
deque<int>ord;//coada

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

}

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


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

    while(!ord.empty())//afisare coada
        {
            g<<ord.back()<<" ";
            ord.pop_back();
        }

    return 0;
}