Cod sursa(job #3275147)

Utilizator Codrut_NeagNeag Codrut Serban Codrut_Neag Data 9 februarie 2025 12:49:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>

using namespace std;

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

int n, m, t[2][100001], start[100001], grad[50001], st[50001], vf, R[50001], r;

void citire()
{
    int x, y;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>t[0][i];
        grad[t[0][i]]++;
        t[1][i]=start[x];
        start[x]=i;
    }
}

void inceput()
{
    for(int i=1; i<=n; i++)
        if(grad[i]==0)
            st[++vf]=i;
}

void sortare()
{
    int x;
    while(vf)
    {

        x=st[vf--];
        int man=start[x];
        while(man)
        {
            grad[t[0][man]]--;
            if(grad[t[0][man]]==0)
                st[++vf]=t[0][man];
            man=t[1][man];
        }
        R[++r]=x;
    }
}

void afisare()
{
    for(int i=1; i<=r; i++)
        out<<R[i]<<" ";
}

int main()
{
    citire();
    inceput();
    sortare();
    afisare();
    return 0;
}