Cod sursa(job #1719757)

Utilizator vancea.catalincatalin vancea.catalin Data 20 iunie 2016 11:37:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define DX 100500
using namespace std;
fstream fin("sortaret.in",ios::in),fout("sortaret.out",ios::out);
vector<int> v[DX];
queue<int> qu;
int ap[DX],bif[DX];
int main()
{
    int i,b,c,aux,n,m,a;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        ap[b]++;
    }
    for(i=1;i<=n;i++) if(ap[i]==0) qu.push(i);
    while(!qu.empty())
    {
        aux=qu.front();
        qu.pop();
        if(bif[aux]) continue;
        bif[aux]=1;
        fout<<aux<<" ";
        for(i=0;i<v[aux].size();i++)
        {
            ap[v[aux][i]]--;
            if(bif[v[aux][i]]==0 && ap[v[aux][i]]==0)
            {
                qu.push(v[aux][i]);
            }
        }
    }
}