Cod sursa(job #1996533)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 1 iulie 2017 19:08:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int N,M;
int p,u,C[100003],d[100003];

struct nod
{
    int info;
    nod* urm;
}*pt[100003];

void InserareNod(nod* &point,int val)
{
    nod* cap = new nod;
    cap->info = val;
    cap->urm = point;
    point = cap;
}

void BF()
{
    u = p;
    p = 1;

    while( p <= u )
    {
        nod* cap = pt[C[p]];

        while( cap != NULL )
        {
            d[cap->info]--;

            if( d[cap->info] == 0 )
                C[++u] = cap->info;

            cap = cap->urm;
        }
        p++;
    }
    for(int i = 1 ; i <= N ; i++)
        g<<C[i]<<' ';
}

int main()
{
    int x,y;
    f>>N>>M;

    for(int i = 1 ; i <= N ; i++)
        pt[i] = NULL;

    for(int i = 1 ; i <= M ; i++)
    {
        f>>x>>y;
        InserareNod(pt[x],y);
        d[y]++;
    }

    for(int i = 1 ; i <= N ; i++)
    {
        if( d[i] == 0 )
            C[++p] = i;
    }
    BF();

    return 0 ;
}