Cod sursa(job #2421042)

Utilizator raduandreiRadu Andrei raduandrei Data 13 mai 2019 23:01:21
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define NMAX 50000
#define MMAX 100000
using namespace std;
int Q[NMAX+1],u;
int gr[MMAX+1];
int n,m;
struct nod
{
    nod *urm;
    int info;
} *a[100001];

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
void add(nod* &prim, int x)
{
    nod*p=new nod;
    p->info=x;
    p->urm=prim;
    prim=p;
}
void sortaret()
{
    for(int i=1; i<=n; ++i)
    if(gr[i]==0) Q[++u]=i;
    for(int i=1; i<=n; ++i)
    {
        int x=Q[i];
        for(nod*q=a[x]; q; q=q->urm)
        {
            int y=q->info;
            gr[y]--;
            if(gr[y]==0) Q[++u]=y;
        }
    }
}
void citire()
{  int x,y;
    fin>>n>>m;
    {
        for(int i=1; i<=m; ++i)
        {
            fin>>x>>y;
            add(a[x],y);
            gr[y]++;
        }
    }

}

int main()
{
    citire();
    sortaret();
    for(int i=1; i<=n; ++i)
        fout<<Q[i]<<" ";
    return 0;
}