Cod sursa(job #1881562)

Utilizator VicktorVictor Teodor Stoian Vicktor Data 16 februarie 2017 16:32:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstdio>

using namespace std;

ofstream cout("sortaret.out");

int viz[50001],v[50001],p,u,n,m,Q[300005];

struct nod{
    nod *urm;
    int inf;
}*L[50001];

inline void add(int a, int b){
    nod *p= new nod;
    p->inf=b;
    p->urm=L[a];
    L[a]=p;
}
inline void sortare(){
    nod *q;
    int curent;
    viz[Q[1]]=1;
    while(p<=u){
        curent=Q[p++];
            cout<<curent<<' ';
        for(q=L[curent];q;q=q->urm)
            if(!viz[q->inf]){
                    --v[q->inf];
            if(!v[q->inf])
                Q[++u]=q->inf,viz[q->inf]=1;
            }
        L[curent]=NULL;
    }
}

int main()
{
    int i,a,b;
    FILE*fin=freopen("sortaret.in","r",stdin);
    scanf("%d%d",&n,&m);
    p=1;
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
        v[b]++;
    }
    for(i=1;i<=n;i++)
        if(!v[i])
            Q[++u]=i;
    sortare();
    return 0;
}