Cod sursa(job #1998622)

Utilizator teodoranTeodora Nemtanu teodoran Data 8 iulie 2017 16:07:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#define nmax 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m;
int q[nmax], pr, ul, d[nmax];
struct nod{
    int info;
    nod*urm;
    }*a[nmax];

void add(nod *&prim, int x){
    nod *p= new nod;
    p->info= x;
    p->urm= prim;
    prim= p;
    }

void read(){
    int x, y, i;
    fin>> n>> m;
    for(i=1; i<=m; i++){
        fin>> x>> y;
        add(a[x], y);
        d[y]++;
        }
    }

void solve(){
    int i, x;
    pr=1;
    for(i=1; i<=n; i++)
        if(d[i]== 0) q[++ul]= i;
    for(i=1; i<=n; i++){
        x= q[i];
        for(nod *p=a[x]; p; p=p->urm){
            d[p->info]--;
            if(d[p->info]==0) q[++ul]= p->info;
            }
        }
    }

void print(int a[], int n){
    int i;
    for(i=1; i<=n; i++)
        fout<< a[i]<<" ";
    fout<< "\n";
    }

int main(){
    read();
    solve();
    print(q, ul);
    return 0;
    }