Cod sursa(job #800647)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 22 octombrie 2012 11:35:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

vector<int> a[51111];
int c[51111],nr[51111];

int main()
{
    int n,m,i,p,q,st,dr=0;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>p>>q;
        a[p].push_back(q);
        nr[q]++;
    }
    for(i=1;i<=n;++i)
    {
        if(nr[i]==0)
        {
            c[++dr]=i;
        }
    }
    st=1;
    while(st<=dr)
    {
        for(i=0;i<a[c[st]].size();++i)
        {
            nr[a[c[st]][i]]--;
            if(nr[a[c[st]][i]]==0)
                c[++dr]=a[c[st]][i];
        }
        out<<c[st]<<" ";
        ++st;
    }
    out<<"\n";
    return 0;
}