Cod sursa(job #1383703)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 10 martie 2015 16:04:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#define MX 50001
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
vector<int> v[MX];
int d[MX], q[MX], st,dr;

void BFS()
{
    st = 1;
    int u;
    vector<int>::iterator it;

    while(st <= dr)
    {
        u = q[st++];
        for(it=v[u].begin(); it!=v[u].end(); it++)
        {
            d[*it]--;
            if(!d[*it])
            {
                q[++dr] = *it;
                fout<<*it<<' ';
            }
        }
    }
}

int main()
{
    int i,x,y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        d[y]++;
    }

    dr = 0;
    for(i=1; i<=n; i++)
    {
        if(!d[i])
        {
            q[++dr] = i;
            fout<<i<<' ';
        }
    }

    BFS();

    fin.close(); fout.close();
    return 0;
}