Cod sursa(job #1975738)

Utilizator gorneanu.andreiFMI Gorneanu Andrei gorneanu.andrei Data 1 mai 2017 20:15:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#define MAXN 50005
using namespace std;

int n, m;
vector<int> lista[MAXN];
int grad_int[MAXN];

void read(){

    fstream f("sortaret.in",ios::in);
    f >> n >> m;

    for(int i = 1;i <= n; ++i)
        grad_int[i] = 0;

    int a, b;

    while(f >> a >> b){
        ++grad_int[b];
        lista[a].push_back(b);
    }
}

void print(vector<int> v){

    fstream g("sortaret.out",ios::out);
    int len = v.size();

    for(int i = 0;i < len; ++i)
        g << v[i] << " ";
}


void solve(){

    vector<int> sortare;
    queue<int> q;

    for(int i = 1;i <= n; ++i)
        if(!grad_int[i])
            q.push(i);


    while(!q.empty()){

        int top = q.front();
        sortare.push_back(top);
        q.pop();
        int len = lista[top].size();

        for(int i = 0;i < len; ++i){
            int nod = lista[top][i];
            --grad_int[nod];
            if(!grad_int[nod])
                q.push(nod);
        }
    }

    print(sortare);
}



int main(){

    read();
    solve();
    return 0;
}