Cod sursa(job #1625547)

Utilizator pusi23Faier Andreea pusi23 Data 2 martie 2016 19:37:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m,i,j,u,v,g[50009],cd[50009],pr,ul;
struct nod
{
    int vecin;
    nod *adr;
};
nod *lv[50009],*p;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v;
        g[v]++;
        p=new nod;
        p->vecin=v;
        p->adr=lv[u];
        lv[u]=p;
    }
    pr=1;
    ul=0;
    for(i=1;i<=n;i++)
    {
        if(g[i]==0)
        {
            ul++;
            cd[ul]=i;
            g[i]=-1;
        }
    }
    while(pr<=ul)
    {
        u=cd[pr];
        fout<<u<<" ";
        for(p=lv[u];p!=0;p=p->adr)
        {
            v=p->vecin;
            g[v]--;
            if(g[v]==0)
            {
                ul++;
                cd[ul]=v;
                g[v]--;
            }
        }
        pr++;
    }
    fin.close();
    fout.close();
    return 0;
}