Cod sursa(job #2018308)

Utilizator cristian_99Olaru Cristian cristian_99 Data 4 septembrie 2017 14:18:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

const int NodMax=100009;
vector < int > v[NodMax];
queue < int > q;

int n,m;
int vec[NodMax];

void citire ()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int a,b;
        fin>>a>>b;
        vec[b]++;
        v[a].push_back(b);
    }
}

void solve ()
{
    for (int i=1;i<=n;i++)
        if (vec[i]==0)
            q.push(i);
    while(!q.empty())
    {
        int nod;
        nod=q.front();
        vector < int > ::iterator it;
        for (it=v[nod].begin(); it!=v[nod].end(); ++it)
        {
            vec[*it]--;
            if (vec[*it]==0) q.push(*it);
        }
        fout<<nod<<" ";
        q.pop();
    }
}

int main()
{
    citire();
    solve();
    return 0;
}