Cod sursa(job #1104535)

Utilizator FayedStratulat Alexandru Fayed Data 10 februarie 2014 20:49:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <vector>
#define NMAX 50001
using namespace std;

int q[NMAX];
int grad[NMAX];
vector < vector < int > > Graf;
int n,m;

void read(){

    int x,y;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    for(register int i=1;i<=m;++i){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        ++grad[y];
    }
}

void topologic(){


    for(register int i=1;i<=n;++i)
        if(!grad[i])
            q[++q[0]] = i;


   int nod;
   for(register int i=1;i<=n;++i){

        nod = q[i];
            for(vector<int>::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it){

                --grad[*it];
                    if(!grad[*it])
                        q[++q[0]] = *it;
            }


   }
}

void write(){

    for(register int i=1;i<=n;++i)
        printf("%d ",q[i]);
}

int main(){

    read();
    topologic();
    write();

return 0;
}