Cod sursa(job #599051)

Utilizator nervousNervous nervous Data 27 iunie 2011 21:22:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

#define X1 50001

using namespace std;

ifstream in;
ofstream out;

vector <int> v[X1];
int grad[X1];
queue <int> q;

inline void bf(int nod)
{
    for(vector <int>::iterator it=v[nod].begin();it!=v[nod].end();++it)
    {
        --grad[*it];
        if(grad[*it]==0) q.push(*it);
    }
}

int main()
{
    int M,N,x,y,nod;

    memset(grad,0,sizeof(grad));

    in.open("sortaret.in");
    in>>N>>M;
    for(;M;--M)
    {
        in>>x>>y;
        v[x].push_back(y);
        ++grad[y];
    }
    in.close();

    for(int i=1;i<=N;++i)
        if(!grad[i]) q.push(i);

    out.open("sortaret.out");
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        out<<nod<<' ';
        bf(nod);
    }
    out<<'\n';
    out.close();

    return 0;
}