Cod sursa(job #1787066)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 24 octombrie 2016 08:47:34
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

ifstream f ("sortaret.in");
ofstream t ("sortaret.out");

struct nod{
int pos;
int intrare;
int iesire;
vector <int> vecini;};

vector <nod> v;
vector <int> sol,poz;
queue <int> q;
int n,m;

void bfs(int nod){int curent;
    v[nod].intrare=-1;
    q.push(nod);
    while (!q.empty()){
    curent=q.front();
    q.pop();
        for (unsigned i=0;i<v[curent].vecini.size();++i){
            if (v[poz[v[curent].vecini[i]]].intrare>0)
            --v[poz[v[curent].vecini[i]]].intrare;
            if (v[poz[v[curent].vecini[i]]].intrare==0){
            q.push(v[poz[v[v[curent].vecini[i]].pos]].pos);
            sol.push_back(v[poz[v[v[curent].vecini[i]].pos]].pos);
            v[poz[v[curent].vecini[i]]].intrare=-1;}}
    }
}

int main()
{   int x,y;
    f>>n>>m;
    v.resize(n);
    for (int i=0;i<n;++i)
        v[i].pos=i;
    for (int i=0;i<m;++i){
        f>>x>>y;
        --x;
        --y;
        v[x].vecini.push_back(y);
        ++v[x].iesire;
        ++v[y].intrare;
    }
    poz.resize(n);
    sort(v.begin(),v.end(),[](nod a,nod b){return a.intrare<b.intrare;});
    for (int i=0;i<n;++i)
        poz[v[i].pos]=i;
    for (auto i:v)
        if (!i.intrare){
            sol.push_back(i.pos);
            bfs(i.pos);
        }
    for (auto i:sol)
        t<<1+i<<" ";
    return 0;
}