Cod sursa(job #791273)

Utilizator lucian666Vasilut Lucian lucian666 Data 23 septembrie 2012 17:09:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb


//Vasilut
#include<fstream>
#include<vector>
#include<queue>

#define NN 50001
#define pb push_back

using namespace std;
ofstream out("sortaret.out");

vector<int>G[NN],list;
typedef vector<int>:: iterator IT ;
queue<int>Q;

int di[NN],n,m;

void read();
void topo();
void write();

int main()
{
    read();
    topo();
    write();
    return 0;
}

void read()
{
    ifstream in("sortaret.in");
    in>>n>>m;
    for(int x,y; m ; --m)
    {
        in>>x>>y;
        G[x].pb(y);
        di[y]++;
    }
}

void topo()
{
    for(int i=1;i<=n;i++)
        if(!di[i])
            Q.push(i);
                while(!Q.empty())
                {
                    int k=Q.front();
                    list.pb(k);
                        for(IT I=G[k].begin();I!=G[k].end();++I)
                        {
                            di[*I]--;
                if(di[*I] ==0 )
                    Q.push(*I);
                        }
                        Q.pop();
                }
}

void write()
{
    for(IT I=list.begin();I!=list.end();++I)
        out<<*I<<" ";
}