Cod sursa(job #2170981)

Utilizator dacianouaPapadia Mortala dacianoua Data 15 martie 2018 10:42:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <iostream>
#define maxn 50010
#define maxm 100010
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m,deg[maxn],Q[maxn];
struct nod
{
    int info;
    nod *urm;
}*v[maxn+5],*c,*e[maxn+5];
void solve()
{
    int x;
    for(int i=1;i<=n;i++)
        if(deg[i]==0)
        Q[++Q[0]]=i;
    nod *d;
    for(int i=1;i<=n;i++)
    {
        x=Q[i];
        d=v[x];
        while(d->urm)
        {
            d=d->urm;
            deg[d->info]--;
            if(deg[d->info]==0)
                Q[++Q[0]]=d->info;
        }
    }
}
int main()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->urm=0;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        if(!v[x]->urm)
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            v[x]->urm=c;
            e[x]=c;
        }
        else
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            e[x]->urm=c;
            e[x]=c;
        }
        deg[y]++;
    }
    solve();
    for(int i=1;i<=n;i++)
        fout<<Q[i]<<" ";
    return 0;
}