Cod sursa(job #2289499)

Utilizator ianiIani Biro iani Data 24 noiembrie 2018 18:04:40
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

struct nod
{
    int data;
    nod* next;
}*a[50005];

int nrintrari[50005],vec[50005],k,ap[50005];

queue<int> q;

int main()
{
    int n,m;
    fin>>n>>m;
    for (int var=1;var<=m;var++)
    {
        int x,y;
        fin>>x>>y;
        nod* g=new nod;
        g->data=y;
        nrintrari[y]++;
        g->next=a[x];
        a[x]=g;
    }
    for (int i=1;i<=n;i++)
        if (nrintrari[i]==0)
            q.push(i);
    while (!q.empty())
    {
        int elem=q.front();
        q.pop();
        vec[++k]=elem;
        ap[elem]=true;
        nod *it=a[elem];
        while(it!=NULL)
        {
            if (ap[it->data])
                continue;
            nrintrari[it->data]--;
            if (nrintrari[it->data]==0)
                q.push(it->data);
            it=it->next;
        }
    }
    for (int i=1;i<=k;i++)
        fout<<vec[i]<<' ';
    return 0;
}